class Solution {
public:
    int aim, ret;

    int findTargetSumWays(vector<int>& nums, int target) 
    {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }   

    void dfs(vector<int>& nums, int pos, int path)
    {
        if(pos == nums.size())
        {
            if(aim == path)
                ret++;
            return ;
        }

        //分别处理加法和减法
        dfs(nums, pos + 1, path + nums[pos]);
        dfs(nums, pos + 1, path - nums[pos]);

    }
};

// 目标和 version 2
class Solution {
public:
    int aim, ret, path;
    //aim用于标记目标和
    //ret用于保存结果
    //path用于记录路径和

    int findTargetSumWays(vector<int>& nums, int target) 
    {
        aim = target;
        dfs(nums, 0);
        return ret;
    }   

    void dfs(vector<int>& nums, int pos)
    {
        if(pos == nums.size())
        {
            if(aim == path)
                ret++;
            
            return ;//记得回溯
        }

        //分别处理加法和减法
        path += nums[pos];
        dfs(nums, pos + 1);
        path -= nums[pos];//恢复现场

        path -= nums[pos];
        dfs(nums, pos + 1);
        path += nums[pos];//恢复现场

    }
};

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int aim;

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        aim = target;
        dfs(candidates, 0, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos, int sum)
    {
        if(aim == sum)
        {
            ret.push_back(path);
            return;
        }
        if(sum > aim || pos == nums.size())
            return;
        
        // for(int i = pos; i < nums.size(); i++)
        // {
        //     path.push_back(nums[i]);
        //     dfs(nums, i, sum + nums[i]);
        //     path.pop_back();
        // }
    
        //枚举个数 v2
        for(int i = 0; i * nums[pos] + sum <= aim; i++)
        {
            if(i) 
                path.push_back(nums[pos]);
            dfs(nums, pos + 1 ,sum + i * nums[pos]);
        }

        for(int i = 1; i * nums[pos] + sum <= aim; i++)
            path.pop_back();
    }
};

//字母大小写全排列
class Solution {
public:
    string path;
    vector<string> ret;


    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ret;
    }

    void dfs(string s, int pos)
    {
        if(pos == s.size())
        {
            ret.push_back(path);
            return;
        }
        
        char ch = s[pos];
        //不改变
        path.push_back(ch);
        dfs(s, pos + 1);
        path.pop_back();//恢复现场

        //改变
        if(ch < '0' || ch > '9')
        {
            ch = change(ch);
            path.push_back(ch);
            dfs(s, pos + 1);
            path.pop_back();//恢复现场
        }

    }

    char change(char ch)
    {
        if(ch >='a' && ch <= 'z') ch -= 32;
        else ch += 32;
        return ch;
    }
};

//优美排列
class Solution {
public:
    bool cheak[16]; //用于去重
    int ret;

    int countArrangement(int n) 
    {
        dfs(1, n);
        return ret;
    }

    void dfs(int pos, int n)
    {
        if(pos == n+1)//下标从1 开始
        {
            ret++;
            return;
        }

        for(int i = 1; i <= n; i++)
        {
            if(!cheak[i] && (i % pos == 0 || pos % i == 0))
            {
                cheak[i] = true;
                dfs(pos+1, n);
                cheak[i] = false;//恢复现场
            }
        }
    }
};

//电话号码的排列组合
class Solution {
public:
    string hash[10] = {"","","abc", "def","ghi","jkl", "mno","pqrs", "tuv", "wxyz"};
    vector<string> ret;
    string path;
    vector<string> letterCombinations(string digits) 
    {
        if(digits.size() == 0) return ret;
        dfs(digits, 0);
        return ret;
    }

    void dfs(string digits, int pos)
    {
        if(digits.size() == pos)
        {
            ret.push_back(path);
            return;
        }
        for(auto ch : hash[digits[pos] - '0'])
        {
            path.push_back(ch);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};

//N皇后

class Solution {
public:
    vector<vector<string>> ret;
    vector<string> path;
    bool checkCol[10]; //列
    bool checkDigi1[20];//主对角线
    bool checkDigi2[20];//附对角线 
    int n;

    vector<vector<string>> solveNQueens(int _n) 
    {
        n = _n;
        //初始化一下棋盘
        path.resize(n);
        for(int i = 0; i < n; i++)
        {
            path[i].append(n, '.');
        }

        dfs(0);
        return ret;
    }

    void dfs(int row)
    {
        if(row == n)
        {
            ret.push_back(path);
            return;
        }

        for(int col = 0; col < n; col++)
        {
            //剪枝
            //checkDigi1[col - row + n] 
            //正对角线可能会存在纵坐标-横坐标为负数的情况，+n是为了避免下标为负数
            if(!checkCol[col] && !checkDigi1[col - row + n] && !checkDigi2[row + col])
            {
                path[row][col] = 'Q';
                checkCol[col] = checkDigi1[col - row + n] = checkDigi2[row + col] = true;
                dfs(row + 1);

                //恢复现场
                path[row][col] = '.';
                checkCol[col] = checkDigi1[col - row + n] = checkDigi2[row + col] = false;
            }
        }
    }
};

//有效的数独
class Solution {
public:
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];

    bool isValidSudoku(vector<vector<char>>& board) 
    {
        for(int i = 0; i < 9; i++)
        {
            for(int j = 0; j < 9; j++)
            {
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    if(row[i][num] || col[j][num] || grid[i/3][j/3][num])
                    {
                        return false;
                    }
                    else
                    {
                        row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                    }
                }
               
            }
        }
        return true;
    }
};

//解数独
class Solution 
{
public:
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
    void solveSudoku(vector<vector<char>>& board) 
    {
        for(int i = 0; i < 9; i++)
        {
            for(int j = 0; j < 9; j++)
            {
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                }
            }
        }

        dfs(board);
    }
    bool dfs(vector<vector<char>>& board)
    {
        
        for(int i = 0; i < 9; i++)
        {
            for(int j = 0; j < 9; j++)
            {
                if(board[i][j] == '.')
                {
                    for(int k = 1; k <= 9; k++)
                    {
                        if(!row[i][k] && !col[j][k] && !grid[i/3][j/3][k])
                        {
                            board[i][j] = '0' + k;
                            row[i][k] = col[j][k] = grid[i/3][j/3][k] =true;
                            if(dfs(board)) return true; //说明这个位置添这个数没问题

                            //恢复现场
                            board[i][j] = '.';
                            row[i][k] = col[j][k] = grid[i/3][j/3][k] =false;
                        }
                       
                    }
                    return false; //说明1-9没有合适的数
                }
            }
        }
        return true;//结果正确
    }
};

//最小栈
class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        st.push(val);
        if(min_st.empty() || val <= min_st.top())
            min_st.push(val);
        
    }
    
    void pop() {
        int top = st.top();
        st.pop();
        if(top == min_st.top())
            min_st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.top();
    }
    stack<int> st;
    stack<int> min_st;
};

//判断栈的弹出序列是否合法
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        int pushi = 0, popi = 0;
        stack<int> st;
        while(pushi < pushV.size())
        {
            st.push(pushV[pushi++]);
            if(st.top() != popV[popi])
            {
                continue;
            }
            else 
            {
                while(!st.empty() && st.top() == popV[popi])
                {
                    st.pop();
                    popi++;
                }
            }
        }

        return st.empty();
    }
};

//基础计算机
class Solution {
public:
    int calculate(string s) 
    {
        stack<char> st;
        int num = 0, ret = 0,  op = 1;
        st.push(op);

        for(char c : s)
        {
            if(c == ' ') continue;
            else if(c >= '0') num = num * 10 + (c - '0');
            else
            {
                ret += op * num;
                num = 0;

                if(c == '+') op = st.top();
                else if(c == '-') op = -st.top();
                else if(c == '(') st.push(op);
                else st.pop(); 
            }
        }

        return ret + op * num;
    }
};

//单词搜索
class Solution {
public:
    bool visi[6][6];
    int m,n;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    bool exist(vector<vector<char>>& board, string word) 
    {
        m = board.size();
        n = board[0].size();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] == word[0])
                {

                    visi[i][j] = true;
                    if(dfs(board, i, j, word, 1)) return true;
                    visi[i][j] = false;
                }
            }
        }
        return false;;
    }

    bool dfs(vector<vector<char>>& board, int i, int j, string& s, int pos)
    {
        if(pos == s.size())
        {
            return true;
        }

        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x>=0 && x < m && y >= 0 && y < n && board[x][y] == s[pos] && !visi[x][y])
            {
                visi[x][y] = true;
                if(dfs(board, x, y, s, pos+1)) return true;
                visi[x][y] = false;
            }
        }

        return false;
    }
};

class Solution {
public:
    bool visi[15][15];
    int m,n;
    int dx[4] = {0,0,-1,1};
    int dy[4] = {1,-1,0,0};
    int ret;
    int getMaximumGold(vector<vector<int>>& grid) 
    {
        m = grid.size(), n = grid[0].size();

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] != 0)
                {
                    visi[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    visi[i][j] = false;
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<int>>& grid, int i, int j, int path)
    {
        ret = max(ret, path);

        for(int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && !visi[x][y] && grid[x][y] != 0)
            {
                visi[x][y] = true;
                dfs(grid, x, y, path + grid[x][y]);
                visi[x][y] = false;
            }
        }
    }
};

class Solution {
public:
    bool visi[20][20];
    int dx[4] = {0,0,1,-1};
    int dy[4] = {-1,1,0,0};
    int ret,m,n,step;
    int uniquePathsIII(vector<vector<int>>& grid) 
    {
        m = grid.size();
        n = grid[0].size();
        int x,y;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 0)
                    step++;
                else if(grid[i][j] == 1)
                {
                    x = i;
                    y = j;
                }

            }
        }
        step += 1;
        visi[x][y] = true;
        dfs(grid, x, y, 0);
        return ret;
    }
    void dfs(vector<vector<int>>& g, int i, int j, int count)
    {
        if(g[i][j] == 2)
        {
            if(count == step)
                ret++;

            return;
        }

        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visi[x][y] && g[x][y] != -1)
            {
                visi[x][y] = true;
                dfs(g, x, y, count + 1);
                visi[x][y] = false;
            }
        }

    }
};

//图像渲染dfs
class Solution {
public:
    int dx[4] ={0,0,-1,1};
    int dy[4] ={1,-1,0,0};
    int m, n;
    int prev;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        m = image.size(), n = image[0].size();
        //判断边界情况
        if(image[sr][sc] == color)  return image;
        prev = image[sr][sc];
        dfs(image, sr, sc, color);
        return image;
    }

    void dfs(vector<vector<int>>& image, int i, int j, int color)
    {   
        image[i][j] = color;

        for(int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
            {
                dfs(image, x, y, color);
            }
        }
    }
};

class Solution {
public:
    int dx[4] = {0,0,-1,1};
    int dy[4] = {1,-1,0,0};
    int m,n,ret = 0;
    bool visi[300][300];
    int numIslands(vector<vector<char>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!visi[i][j] && grid[i][j] == '1')
                {
                    ret++;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        visi[i][j] = true;

        for(int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && !visi[x][y] && grid[x][y] == '1')
            {
                dfs(grid, x, y);
            }
        }
    }
};

//岛屿面积

class Solution {
public:
    int ret = 0,m,n,path;
    int dx[4] = {0,0,-1,1};
    int dy[4] = {1,-1,0,0};
    bool visi[50][50];
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; j++)
            {
                if(!visi[i][j] && grid[i][j] == 1)
                {
                    path = 0;
                    dfs(grid, i, j);
                }
            }
        }

        return ret;
    }

    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        visi[i][j] = true;
        path++;
        ret = max(ret, path);

        for(int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && !visi[x][y] && grid[x][y] == 1)
            {
                dfs(grid, x, y);
            }
        }
    }
};

//被围绕的区域
class Solution {
public:
    int m,n;
    int dx[4] = {0,0,-1,1};
    int dy[4] = {1,-1,0,0};

    void solve(vector<vector<char>>& board) 
    {
        m = board.size(), n = board[0].size();
        
        //1、将边界的'O'修改成'.'特殊标记一下
        for(int i = 0; i < n; i++)
        {
            if(board[0][i] == 'O') dfs(board, 0, i);
            if(board[m - 1][i] == 'O') dfs(board, m - 1, i);
        }
        for(int j = 0; j < m; j++)
        {
            if(board[j][0] == 'O') dfs(board, j, 0);
            if(board[j][n - 1] == 'O') dfs(board, j, n - 1);
        }

        //2、将'.'还原成'O', 将'O'修改成'X'。
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] == '.')
                    board[i][j] = 'O';
                else if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = '.';
       
        for(int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n  && board[x][y] == 'O')
            {
                dfs(board, x, y);
            }
        }
    }
};

class Solution {
public:
    bool visiP[200][200];
    bool visiA[200][200];
    int dx[4] = {0,0,-1,1};
    int dy[4] = {1,-1,0,0};
    int m,n;

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) 
    {
        vector<vector<int>> ret;
        m = heights.size(), n = heights[0].size();

        //从边界位置出发，找>=我这个位置的
        for(int i = 0; i < n; i++)
        {
            if(!visiP[0][i])
                dfsP(heights,0,i);
        }
        for(int i = 0; i < m; i++)
        {
            if(!visiP[i][0])
                dfsP(heights,i,0);
        }

        for(int i = 0; i < n; i++)
        {
            if(!visiA[m-1][i])
                dfsA(heights,m - 1,i);
        }

        for(int i = 0; i < m; i++)
        {
            if(!visiA[i][n-1])
                dfsA(heights,i,n - 1);
        }

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(visiA[i][j] && visiP[i][j])
                    ret.push_back({i, j});
            }
        }

        return ret;
    }
    void dfsP(vector<vector<int>>& heights, int i, int j)
    {
        visiP[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && !visiP[x][y] && (heights[i][j] <= heights[x][y]))
            {
                dfsP(heights, x, y);
            }
        }
    }

    void dfsA(vector<vector<int>>& heights, int i, int j)
    {
        visiA[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && !visiA[x][y] && (heights[i][j] <= heights[x][y]))
            {
                dfsA(heights, x, y);
            }
        }
    }
};

//扫雷游戏
class Solution {
public:
    int dx[8] = {0,0,-1,1,1,1,-1,-1};
    int dy[8] = {-1,1,0,0,1,-1,1,-1};
    int m, n;
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        int i = click.front(), j = click.back();
        if(board[i][j] == 'M')
        {
            board[i][j] = 'X';
            return board;
        }
        //挖到空格
        dfs(board, i, j);
        
        return board;
    }


    void dfs(vector<vector<char>>& board, int i, int j)
    {
        int count = 0;
        for(int k = 0; k < 8; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
            {
                count++;
            }
        }

        if(count)
        {
            board[i][j] = '0' + count;
            return;
        }
        else
        {
            board[i][j] = 'B';
            for(int k = 0; k < 8; k++)
            {
                int x = dx[k] + i, y = dy[k] + j;
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
                {
                    dfs(board, x, y);
                }
            }
        }
        
        }
};

//机器人移动范围
class Solution {
public:
    int ret;
    int m, n;
    bool visi[100][100];
    int digit(int i)
    {
        int sum = 0;
        while(i)
        {
            sum += (i % 10);
            i /= 10;
        }

        return sum;
    }

    int wardrobeFinishing(int _m, int _n, int cnt) 
    {
        m = _m, n = _n;
        dfs(0,0,cnt);

        return ret;
    }

    void dfs(int i, int j, int cnt)
    {
        visi[i][j] =true;

        if(digit(i) + digit(j) <= cnt)
        {
            ret++;
        }
        else
        {   
            return;
        }
        if(i < m && j + 1 < n && !visi[i][j + 1])
            dfs(i,j + 1, cnt);
        
        if(i + 1 < m && j < n && !visi[i+1][j])
           dfs(i + 1,j, cnt);
    }
};

//记忆化搜索
class Solution {
    int memory[31]; // 备忘录
public:
    int fib(int n) 
    {
        //初始化备忘录，避免结果有误
        for(int i = 0; i < 31; i++)
            memory[i] = -1;

        return dfs(n);
    }

    int dfs(int n)
    {
        //每次进入递归先去备忘录瞅一瞅
        if(memory[n] != -1) 
            return memory[n];

        if(n == 1 || n == 0)
        {
            memory[n] = n;//返回之前将结果存到备忘录
            return n;
        }

        memory[n] = dfs(n - 2) + dfs(n - 1);//返回之前将结果存到备忘录
        return memory[n];
    }

};

//dp
class Solution {
public:
    int dp[31]; // dp表
    int fib(int n) 
    {
        dp[0] = 0, dp[1] = 1;//初始化dp表

        for(int j = 2; j < 31; j++)
        {
            dp[j] = dp[j - 1] + dp[j - 2]; //状态转移方程
        }

        return dp[n];
    }
};

//记忆化搜索 / 动态规划——不同路径
class Solution {
public:
    int memory[101][101];
    int m,n;
    int uniquePaths(int _m, int _n) 
    {
        //动态规划
        vector<vector<int>> dp(_m + 1, vector<int>(_n + 1));
        dp[1][1] = 1;
        for(int i = 1; i <= _m; ++i)
            for(int j = 1; j <= _n; ++j)
            {
                if(i == 1 && j == 1) continue; // 处理边界情况
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }

            
        return dp[_m][_n];

        //记忆化搜索
        // m = _m, n = _n;
        // return dfs(_m,_n);
    }

    int dfs(int i, int j)
    {
        if(memory[i][j] != 0)
            return memory[i][j];

        if(i == 0 ||  j == 0)
            return 0;
        
        if(i == 1 && j == 1)
        {
            memory[i][j] = 1;
            return memory[i][j];
        }
        
        if(j >= 1 && j < n + 1 && i >= 1 && i < m + 1)
        {
            //向右走
            memory[i][j] = dfs(i, j - 1) + dfs(i - 1, j);
            return memory[i][j];
        }

        return memory[i][j];
    }
};

//最长递增子序列

class Solution {
public:

    int lengthOfLIS(vector<int>& nums) 
    {
        //动态规划
        int n = nums.size();
        vector<int> dp(n, 1); // 创建并初始化dp表
        int ret = 0;
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(nums[j] > nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ret = max(dp[i], ret);
        }

        return ret;

        //记忆化搜索
        // int n = nums.size();
        // int ret = 1;
        // vector<int> memory(n,0);//备忘录
        // for(int i = 0;i < n; i++)
        // {
        //     ret = max(ret, dfs(memory,nums, i));
        // }
        // return ret;
    }

    int dfs(vector<int>& memory,vector<int>& nums, int pos)
    {
        if(memory[pos] != 0)  
            return memory[pos];
        int ret = 1;
        for(int i = pos + 1; i < nums.size(); i++)
        {
            if(nums[pos] < nums[i])
            {
                ret = max(ret,dfs(memory, nums, i) + 1);
            } 
        }
        memory[pos] = ret;
        return memory[pos];
    }
};

//猜数字游戏II
class Solution {
public:
    int memory[201][201];  //初始化背包
    int getMoneyAmount(int n) 
    {
        return dfs(1, n);
    }

    int dfs(int left, int right)
    {
        //处理边界情况
        if(left >= right)
        {
            return 0;
        } 

        if(memory[left][right] != 0)
        {
            return memory[left][right];
        }

        //ret用来存最坏情况的最小值
        int ret = INT_MAX;
        for(int head = left; head <= right; head++)
        {
            int x = dfs(left, head - 1);
            int y = dfs(head+1, right);
            //max(x, y) + head指的是取左右两边较大值+上自己。因为要保证能赢所以取max
            //但是要保证使用最少的钱赢最坏的情况，所以将结果跟ret比较取较小值
            ret = min(ret, max(x, y) + head);
        }

        memory[left][right] = ret;
        return ret;
    }
};

//矩阵中最长递增路径
class Solution {
public:
    int memory[201][201];
    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0};
    int m,n;
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        m = matrix.size(), n = matrix[0].size();
        int ret = 0;
        for(int i = 0;i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                ret = max(ret, dfs(matrix, i , j));
            }
        }
        return ret;
    }

    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if(memory[i][j] != 0)
            return memory[i][j];
        int ret = 1;
        for(int k = 0; k < 4; k++)
        {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[i][j] < matrix[x][y])
            {
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memory[i][j] = ret; 
        return ret;
    }
};

// 三步问题
class Solution {
public:
    int waysToStep(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;
        const int MOD = 1000000007;
        vector<int> dp(n+1); //创建dp表
        dp[1] = 1; dp[2] = 2; dp[3] = 4;
        for(int i = 4; i <= n; i++)
        {
            dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
        }
        return dp[n];
    }
};

//两数组交集
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums1 int整型vector 
     * @param nums2 int整型vector 
     * @return int整型vector
     */
     bool hash[1010] = {0};
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<int> ret;
        
        for(int e : nums1)
        {
            hash[e] = true;
        }

        for(int e : nums2)
        {
            if(hash[e] == true)
            {
                ret.push_back(e);
                hash[e] = false;
            }
        }

        return ret;
    }
};

//最小话费爬楼梯
#include <iostream>

using namespace std;

const int N = 1e5+10;

int cost[N];
int dp[N];

int main() 
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++)
        cin >> cost[i];
    for(int i = 2; i <= n; i++)
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    cout << dp[n] << endl;
}


//解码方案
class Solution {
public:
    int numDecodings(string s) 
    {
        int n = s.size();
        //创建dp表
        vector<int> dp(n,0);

        //初始化
        if(s[0] != '0')
            dp[0] += 1;
        else
            return 0;
        
        if(n == 1)//处理边界情况
            return dp[0];
        
        int t = (s[0] - '0') * 10 + s[1] - '0';
        if(t >= 10 && t <= 26) dp[1]+=1;
        if(s[0] != '0' && s[1] != '0') dp[1]+=1;

        //填表
        for(int i = 2; i < n; i++)
        {
            if(s[i] != '0') // 符合[1,9]
                dp[i] += dp[i - 1];
            int t = (s[i-1] - '0') * 10 + s[i] - '0';
            if(t >= 10 && t <= 26) dp[i] += dp[i-2]; // 符合[10,26]
            
        }

        //返回结果
        return dp[n-1];
    }
};

//不同路径I
class Solution {
public:
    int numDecodings(string s) 
    {
        int n = s.size();
        //创建dp表
        vector<int> dp(n+1);

        //初始化
        dp[0] = 1;
        dp[1] = s[1-1] != '0';
        if(n == 1)//处理边界情况
            return dp[1];


        //填表
        for(int i = 2; i <= n; i++)
        {
            if(s[i - 1] != '0') // 符合[1,9]的情况
                dp[i] += dp[i - 1];
            int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if(t >= 10 && t <= 26) dp[i] += dp[i-2]; // 符合[10,26]的情况
            
        }
        //返回结果
        return dp[n];
    }
};

//不同路径II
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        //创建dp表
        //由于多创建了一行以及多创建一列，需要注意下标映射
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        //初始化
        dp[0][1] = 1;

        //填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                //下标映射关系需要处理
                if(obstacleGrid[i - 1][j - 1] == 1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        //返回值
        return dp[m][n];
    }

//珠宝的最高价值
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) 
    {
        //创建dp表
        int m = frame.size(), n = frame[0].size();

        vector<vector<int>>dp(m + 1, vector<int>(n+1, 0));
        dp[1][1] = frame[1 - 1][1 - 1];
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = frame[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }
};

//下降路径最小和
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix[0].size();
        //创建dp表
        vector<vector<int>>dp(n,vector<int>(n));
        
        //初始化
        for(int i = 0; i < n; i++)
            dp[0][i] = matrix[0][i];

        //填表
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(j == 0)
                    dp[i][j] += (matrix[i][j] + min(dp[i - 1][j], dp[i - 1][j + 1]));
                else if(j == n - 1)
                    dp[i][j] += (matrix[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]));
                else 
                {
                    int m = dp[i - 1][j - 1];
                    if(m > dp[i - 1][j])
                        m = dp[i - 1][j];
                    if(m > dp[i - 1][j + 1])
                        m = dp[i - 1][j + 1];
                    dp[i][j] += (matrix[i][j] +m);
                }
            }
        }

        int ret = INT_MAX;
        for(int i = 0; i < n; i++)
            ret = min(ret, dp[n-1][i]);
        
        return ret;
    }
};

//前k个高频单词
class Solution {
public:
    //由于sort是不稳定的排序，所以我们用仿函数控制比较逻辑
    //当次数一样时，需要按照字典序的降序排序
    struct Greater
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            return kv1.second > kv2.second; //|| ((kv1.second == kv2.second) && kv1.first < kv2.first); 
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        map<string, int> countMap;
        for(auto& s : words)
            countMap[s]++;//字典序排序 + 统计次数
        
        //vector<pair<string, int>> sortV(countMap.begin(), countMap.end());
        //sort(sortV.begin(), sortV.end(), Greater());
        //stable_sort(sortV.begin(), sortV.end(), Greater());

        multimap<int, string, greater<int>> sortMap;
        for(auto& kv : countMap)
            sortMap.insert({kv.second, kv.first});
        
        auto it = sortMap.begin();
        vector<string> ret;
        for(int i = 0; i < k; i++)
        {
            ret.push_back((it->second);
            ++it;
        }
        return ret;


    }
};

// 最小路径和
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        //创建dp表
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));


        //初始化+填表
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                if(i == 1)
                    dp[i][j] = grid[i-1][j-1] + dp[i][j-1];
                else if(j == 1)
                    dp[i][j] = grid[i-1][j-1] + dp[i-1][j];
                else
                    dp[i][j] = grid[i-1][j-1] + min(dp[i-1][j], dp[i][j-1]);
            }
        
        //返回值
        return dp[m][n];
    }
};


//地下城游戏
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        int m = dungeon.size(), n = dungeon[0].size();

        //创建dp表
        vector<vector<int>>dp(m + 1, vector<int>(n + 1, INT_MAX));

        //初始化
        dp[m][n-1] = dp[m-1][n] = 1;

        //填表——顺序为从右下往左上填表
        for(int i = m - 1; i >= 0; i--)
            for(int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j];
                dp[i][j] = max(1,dp[i][j]); //避免负数的情况
            }

        //返回值
        return dp[0][0];
    }
};

//复杂链表的拷贝
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

//按摩师
class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        Node* copyHead = nullptr, *copyTail = nullptr;
        Node* cur = head;
        map<Node*, Node*> copyMap;

        while(cur)
        {
            Node* copyNode = new Node(cur->val);

            if(copyHead == nullptr)
                copyHead = copyTail = copyNode;
            else
            {
                copyTail->next = copyNode;
                copyTail = copyTail->next;
            }
            //保存映射关系
            copyMap[cur] = copyNode;

            cur = cur->next;
        }

        cur = head;
        copyTail = copyHead;

        while(cur)
        {
            //边界情况
            if(cur->random == nullptr)
                copyTail->random = nullptr;
            else
                copyTail->random = copyMap[cur->random];//通过映射关系，将random指针处理
            cur = cur->next;
            copyTail = copyTail->next;
        }

        return copyHead;
    }
};

//打家劫舍2
class Solution 
{
public:
    int massage(vector<int>& nums) 
    {
        
        int n = nums.size();
        //处理边界情况
        if(n == 0) return 0;

        //创建两个dp表,f[i]表示当前位置选
        //g[i] 表示当前位置不选
        vector<int> f(n), g(n);

        //初始化dp表
        f[0] = nums[0];
        g[0] = 0;

        //填表
        for(int i = 1; i < n; i++)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        //返回两个表最后位置较大的值
        return max(f[n - 1], g[n - 1]);
    }
};

class Solution 
{
public:

    int rob1(vector<int>& nums, int left, int right)
    {
        //处理边界情况
        if(left > right) return 0;

        int n = nums.size();
        //创建dp表
        vector<int> f(n), g(n);

        //初始化
        f[left] = nums[left];

        //填表
        for(int i = left; i <= right; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        //返回结果
        return max(g[right], f[right]);

    }

    int rob(vector<int>& nums) {
        int n = nums.size();

        return max(nums[0] + rob1(nums, 2, n-2), rob1(nums, 1, n - 1));
    }
};

//删除并获得点数
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) 
    {
        const int N = 10001;

        //建立一个映射关系表,并初始化
        
        int arr[N] = {0};
    
        for(int e : nums) 
            arr[e] += e;
        //此时，通过arr就能将问题转化成“打家劫舍”。
        
        //创建dp表
        vector<int> f(N), g(N);
        //默认初始化为0，这里无需处理，因为数据大于等于1
        //填表
        for(int i = 1; i < N; i++)
        {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }

        //  返回结果
        return max(f[N-1], g[N-1]);
    }
};

//粉刷房子
class Solution {
public:
    int minCost(vector<vector<int>>& costs) 
    {
        int n = costs.size();
        //创建dp表
        vector<vector<int>> dp(n + 1, vector<int>(3));

        //初始化——虚拟节点为0
        //填表
        for(int i = 1; i <=n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                if(j == 0)
                    dp[i][j] = min(dp[i-1][j + 1], dp[i - 1][j + 2]) + costs[i-1][j];
                else if(j == 1)
                    dp[i][j] = min(dp[i-1][j - 1], dp[i - 1][j + 1]) + costs[i-1][j];
                else
                    dp[i][j] = min(dp[i-1][j - 1], dp[i - 1][j - 2]) + costs[i-1][j];

            }
        }

        //返回结果
        int ret = dp[n][0];
        ret = min(ret,dp[n][1]);
        return min(ret, dp[n][2]);

    }
};

//买卖股票的最佳时期含冷冻期
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        //处理边界情况
        if(n == 1) return 0;
        
        //创建dp表
        vector<vector<int>> dp(n, vector<int>(3));
        //dp[i][0]表示 第i天结束，处于买入状态，此时的最大利润
        //dp[i][1]表示 第i天结束，处于交易状态，此时的最大利润
        //dp[i][2]表示 第i天结束，处于冷冻期状态，此时的最大利润
        
        //初始化
        dp[0][0] = -prices[0];

        //填表
        for(int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i-1][2]);
            dp[i][2] = dp[i-1][0] + prices[i];
        }

        //返回结果
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};
//买卖股票的最佳时期含手续费
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        int n = prices.size();
        //创建dp表
        //f表示买入状态的最大利润
        //g表示卖出状态的最大利润
        vector<int> g(n), f(n);

        //初始化
        f[0] = -prices[0];

        //填表
        for(int i = 1; i < n; ++i)
        {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
        return g[n-1];
    }
};

//买卖股票的最佳时机 III
class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        //创建dp表
        //初始化为-0x3f3f3f3f避免int溢出的问题
        vector<vector<int>> f(n, vector<int>(3, -0x3f3f3f3f)), g(n, vector<int>(3, -0x3f3f3f3f));
        //初始化
        f[0][0] = -prices[0];
        g[0][0] = 0;

        //填表
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                //j存在越界风险
                if(j >= 1) 
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int ret = INT_MIN;
        for(int j = 0; j < 3; j++)
        {
            ret = max(ret, g[n - 1][j]);
        }
        return ret;
    }
};

//买卖股票的最佳时机 IV
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        int n = prices.size();

        //创建dp表
        vector<vector<int>> f(n, vector<int>(k + 1, -0x3f3f3f3f));
        vector<vector<int>> g(n, vector<int>(k + 1, -0x3f3f3f3f));

        //初始化dp表
        f[0][0] = -prices[0];
        g[0][0] = 0;

        //填表
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j <= k; j++)
            {
                //              啥也没干          从交易状态到购买状态
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j]; // 啥也没干
                if(j >= 1) //防止越界              从购买状态到交易状态
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        //返回 g表的最后一行的最大值
        int ret = INT_MIN;
        for(int j = 0; j <= k; j++)
            ret = max(ret, g[n - 1][j]);
        
        return ret;
    }
};

//子数组最大和
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        //创建dp表
        vector<int> dp(n + 1);

        //填表
        int ret = INT_MIN;
        for(int i = 1; i <= n; i++)
        {
            dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
            ret = max(ret, dp[i]);
        }

        //返回结果
        return ret;
    }
};


//环形数组的子数组最大和
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) 
    {
        int n = nums.size();

        //创建dp表
        vector<int> f(n + 1), g(n + 1);
        //f[i]:以i为结尾的子数组最大和
        //g[i]:以i为结尾的子数组最小和

        // 填表
        for(int i = 1; i <= n; i++)
        {
            f[i] = max(nums[i - 1], nums[i - 1] + f[i - 1]);
            g[i] = min(nums[i - 1], nums[i - 1] + g[i - 1]);
        }

        //返回结果
        //分情况讨论，最大子数组和 与 数组和减去最小子数组和  的较大值
        int fmax = INT_MIN;
        int gmin = INT_MAX;
        int sum = 0;

        for(int i = 1; i <= n; i++)
        {
            sum += nums[i - 1];
            fmax = max(fmax, f[i]);
            gmin = min(gmin, g[i]);
        }
        //处理全是负数的情况
        if(sum == gmin) 
            return fmax;
        else
            return max(fmax, sum - gmin);

    }
};
//乘积最大子数组
class Solution {
public:
    int maxProduct(vector<int>& nums) 
    {
        // int n = nums.size();

        // //创建dp表
        // vector<int> f(n + 1), g(n + 1);
        // //f[i]:表示以i为结束的最大乘积
        // //g[i]:表示以i为结束的最小乘积


        // //初始化
        // f[0] = 1;
        // g[0] = 1;
        // //填表
        // for(int i = 1; i <= n; i++)
        // {
        //     //分情况讨论
        //     f[i] = max(nums[i - 1], f[i - 1] * nums[i - 1]);
        //     f[i] = max(f[i], g[i - 1] * nums[i - 1]);

        //     g[i] = min(nums[i-1], f[i - 1] * nums[i - 1]);
        //     g[i] = min(g[i], g[i - 1] * nums[i - 1]);
        // }
        
        // int ret = INT_MIN;
        // for(int i = 1; i <= n; i++)
        //     ret = max(ret, f[i]);
        // //返回结果
        // return ret;

        int n = nums.size();

        //创建dp表
        vector<int> f(n + 1), g(n + 1);
        //f[i]:表示以i为结束的最大乘积
        //g[i]:表示以i为结束的最小乘积

        //初始化
        f[0] = 1;
        g[0] = 1;

        //填表并统计最大值
        int ret = INT_MIN;
        for(int i = 1; i <= n; i++)
        {
            int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1];
            // y在f表中表示nums[i - 1] 大于0的情况，在g表中表示nums[i - 1] 小于0的情况
            // z在f表中表示nums[i - 1] 小于0的情况，在g表中表示nums[i - 1] 大于0的情况
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));
            ret = max(ret, f[i]);
        }
        //返回f表中的最大值即可
        return ret;
    }
};

// 乘积为正数的最长子数组长度
class Solution {
public:
    int getMaxLen(vector<int>& nums) 
    {
        int n = nums.size();

        //创建dp表
        vector<int> f(n + 1), g(n + 1);
        //f[i] 表示以i位置为结尾，所有子数组中乘积为正数的最长子数组长度
        //g[i] 表示以i位置为结尾，所有子数组中乘积为负数的最长子数组长度
        
        //填表
        int ret = INT_MIN;
        for(int i = 1; i <= n; i++)
        {
            if(nums[i - 1] > 0)
            {
               f[i] = f[i - 1] + 1;
               g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
               ret = max(ret, f[i]);
            }
            else if(nums[i - 1] < 0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; 
                g[i] = f[i - 1] + 1;
                ret = max(ret, f[i]);
            }
        }

        //返回结果
        return ret == INT_MIN ? 0 : ret;
    }
};

//等差数列划分 
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        // int n = nums.size();
        
        // //处理边界情况
        // if(n < 3) return 0;

        // //创建dp表
        // vector<int> f(n + 1);
        // //f[i]表示，以i位置为结尾，所有子数组的的等差数列个数

        // int count = 1;
        // int ret = INT_MIN;
        // for(int i = 3; i <= n; i++)
        // {
        //     if(nums[i-1] - nums[i - 2] == nums[i - 2] - nums[i - 3])
        //     {
        //         f[i] = f[i - 1] + count++;
        //     }
        //     else 
        //     {
        //         f[i] = f[i - 1];
        //         count = 1;
        //     }
        //     ret = max(ret, f[i]);
        // }
        // return ret;

        int n = nums.size();

        //创建dp表
        vector<int> dp(n);

        //填表
        int ret = 0;
        for(int i = 2; i < n; i++)
        {
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            ret += dp[i];
        }

        //返回结果
        return ret;
    }
};

// 最长湍流子数组
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) 
    {
        int n = arr.size();

        //处理边界情况
        if(n == 1) return 1;

        //创建dp表
        vector<int> f(n, 1), g(n, 1);
        //f[i］表示：以i位置元素为结尾的所有子数组中, 最后呈现“上升”状态下的最长湍流数组的长度
        //g[i］表示：以i位置元素为结尾的所有子数组中, 最后呈现“下降”状态下的最长湍流数组的长度

        //填表
        int ret = INT_MIN;//统计最长长度
        for(int i = 1; i < n; i++)
        {
            int a = arr[i], b = arr[i - 1];
            if(a > b) //上升
                f[i] = g[i - 1] + 1;
            if(b > a) //下降
                g[i] = f[i - 1] + 1;

            //更新结果
            ret = max(ret, max(f[i], g[i]));
        }

        //返回f表和g表中最大值
        return ret;
    }   
};

//单词划分
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        //创建hash表来快速判断单词在不在字典
        unordered_set<string> hash;
        for(auto &str : wordDict)
            hash.insert(str);

        int n = s.size();

        //创建dp表
        vector<bool> dp(n + 1);
        
        //初始化
        dp[0] = true; //保证后续填表是正确的
        s = ' ' + s;//在字符串的一个位置放个标志符以便dp表填表

        //填表
        for(int i = 1; i <= n; i++)
        {
            for(int j = i; j >= 1; j--)
            {
                if(dp[j - 1] == true && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        //返回结果
        return dp[n];
    }
};

class Solution {
public:
    int findSubstringInWraproundString(string s) 
    {
        int n = s.size();
        
        //创建dp表
        vector<int> dp(n, 1);

        //填表
        for(int i = 1; i <= n; i++)
        {
            if(s[i] - s[i - 1] == 1 || (s[i - 1] == 'z' && s[i] == 'a'))
                dp[i] = dp[i - 1] + 1;
        }   

        //去重，去相同字母的最大值即可
        int hash[26] = {0};
        for(int i = 0; i < n; i++)
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);

        int sum = 0;
        for(int i : hash)
            sum += i;
        //返回结果
        return sum;
    }
};

//最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n = nums.size();

        //创建dp表
        vector<int> dp(n + 1, 1);
        //dp[i]表示，以i位置为结尾时，所有递增子序列的最长长度
        //因为最坏情况下，dp[i]的长度为1，将全部初始化成1，就不需要考虑最坏情况的填表

        //填表
        int ret = INT_MIN;
        for(int i = 0; i < n; i++)
        {
            for(int j = i; j >= 0; j--)
            {
                if(nums[i] > nums[j])
                dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

//摆动序列
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int n = nums.size();

        //  创建dp表
        vector<int> f(n, 1), g(n, 1);
        //f[i]表示，以i位置为结尾的所有子序列中，最后一个位置呈现“上升”趋势的最长摆动序列的长度
        //g[i]表示，以i位置为结尾的所有子序列中，最后一个位置呈现“下降”趋势的最长摆动序列的长度
        
        bool flag = 0;

        int ret = INT_MIN;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] - nums[j] > 0)
                {
                    f[i] = max(g[j] + 1, f[i]);
                }
                else if(nums[i] - nums[j] < 0)
                {
                    g[i] = max(f[j] + 1, g[i]);
                }
            }
            ret = max(ret, max(f[i], g[i]));
        }

        //返回结果
        return ret;
    }
};

//最长递增子序列的个数
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) 
    {
        int n = nums.size();

        //创建dp表并初始化
        vector<int> len(n, 1), count(n, 1);
        //len[i]表示以i位置为结尾，所有子序列中最长递增子序列的长度
        //count[i]表示以i位置为结尾，所有子序列中最长递增子序列的个数

        int retlen = 1, retcnt = 1;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i])
                {
                    
                    if(len[j] + 1 > len[i]) 
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                    else if(len[i] == len[j] + 1) 
                        count[i] += count[j];
                }
            }
            if(retlen == len[i]) 
                retcnt += count[i];
            else if(retlen < len[i])
            {
                retlen = len[i];
                retcnt = count[i];
            }
        }

        return retcnt; 
    }
};

//最长数对链
class Solution {
public:
    
    struct Less
    {
        bool operator()(const vector<int>& vv1, const vector<int>& vv2)
        {
            return vv1[0] < vv2[0];
        }
    };

    int findLongestChain(vector<vector<int>>& pairs) 
    {
        int n = pairs.size();

        //预处理
        vector<vector<int>>nums = pairs;
        sort(nums.begin(), nums.end(), Less());
        //创建dp表 + 初始化
        vector<int> dp(n, 1);

        //填表
        int ret =INT_MIN;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[j][1] < nums[i][0])
                {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
            }
            ret = max(ret, dp[i]);
        }
        return ret == INT_MIN ? 1 : ret;
    }
};

//柠檬水找零
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        // int f = 0, t = 0, tw = 0;
        // for(int i = 0; i < bills.size(); i++)
        // {
        //     if(bills[i] == 10)
        //     {
        //         if(f == 0)
        //             return false;
        //         else
        //         {
        //             f--;
        //             t++;
        //         }
        //     }
        //     else if(bills[i] == 20)
        //     {
        //         if(t > 0 && f > 0) //贪心
        //         {
        //             t--;
        //             f--;
        //             tw++;
        //         }
        //         else if(t == 0 && f > 2)
        //         {
        //             f -= 3;
        //             tw++;
        //         }
        //         else
        //             return false;
        //     }
        //     else 
        //     {
        //         f++;
        //     }
        // }

        // return true;

        int five = 0, ten = 0;
        for(int e : bills)
        {
            if(e == 5) ++five;
            else if(e == 10)
            {
                if(five == 0) return false;
                else
                {
                    --five;
                    ++ten;
                }
            }
            else // 20
            {
                if(ten >= 1 && five >= 1) // 贪心
                {
                    --ten; 
                    --five;
                }
                else if(ten == 0 && five >= 3)
                {
                    five -= 3;
                }
                else return false;
            }
        }
        return true;
    }
};

//将数组和减半的最少操作次数
class Solution {
public:
    int halveArray(vector<int>& nums) 
    {
       priority_queue<double> heap;

        double sum = 0;
        for(auto e : nums)
        {
            heap.push(e);
            sum += e;
        }
    
        sum /= 2.0;
   
        int count = 0;
        while(sum > 0)
        {
            double t = heap.top() / 2;
            heap.pop();
            sum -= t;
            count++;
            heap.push(t);
        }
        return count;
    }
};

//最长定差子序列

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) 
    {
        int n = arr.size();
        
        //创建dp表
        unordered_map<int, int> hash;

        hash[arr[0]] = 1;// 初始化dp表

        int ret = 1;
        for(int i = 1; i < n; i++)
        {
            //当arr[i] - difference不存在，Hash值被设置为1
            //当arr[i] - difference存在， 
            //hash[arr[i] - difference]存着的就是离hash[arr[i]]最近的那个最长定长子序列长度
            hash[arr[i]] = hash[arr[i] - difference] + 1;
            ret = max(ret, hash[arr[i]]);
        }

        return ret;
    }
};

// 最长的斐波那契子序列的长度
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) 
    {
        int n = arr.size();

        //优化：用哈希表快速判断值在不在
        unordered_map<int, int> hash; // 用于快速判断arr[j] - arr[i]的值在不在
        int index = 0;
        for(int e : arr)
            hash[e] = index++;

        //创建dp表
        vector<vector<int>> dp(n,vector<int>(n, 2));
        //dp[i][j]表示以i位置在前，j位置为结尾，所有子序列中最长斐波那契数列的长度



        //填表 —— 从上往下
        int ret = 2;
        for(int j = 2; j < n; j++)
        {
            for(int i = 1; i < j; i++)
            {
                auto it = hash.find(arr[j] - arr[i]);
                if(it != hash.end() && it->second < i) //arr[j] - arr[i]存在，且下标小于i
                {
                    dp[i][j] = dp[it->second][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
        }

        return ret == 2 ? 0 : ret;

    }
};

//最大数
class Solution {
public:
    struct Less
    {
        bool operator()(const string& s1, const string& s2)
        {
            return s1 + s2 > s2 + s1;
        }
    };
    string largestNumber(vector<int>& nums) 
    {
        vector<string> arr;
        for(auto e : nums)
            arr.push_back(to_string(e));
        
        sort(arr.begin(), arr.end(), Less());
        
        string ret = "";
        for(auto& e : arr)
            ret += e;
        
        if(ret[0] != '0')
            return ret;
        else 
            return "0";
    }
};

//最长等差数列
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) 
    {
        int n = nums.size();
        
        //优化：用哈希表存数据和下标的映射
        unordered_map<int, int> hash;
        hash[nums[0]] = 0; //初始化1，方便填表

        //创建dp表
        vector<vector<int>> dp(n, vector<int>(n, 2));
        //dp[i][j]表示，以i在前j在后的所有子序列中，最长等差数列的长度

        int ret = 2;

        for(int i = 1; i < n - 1; i++)//固定中间的数
        {     
            for(int j = i + 1; j < n; j++)
            {
                int a = 2 * nums[i] - nums[j];
                if(hash.count(a)) //符合等差数列
                    dp[i][j] = dp[hash[a]][i] + 1;
                
                ret = max(ret, dp[i][j]);//更新结果
            }
            hash[nums[i]] = i; // 将数据丢进哈希表，方便找最近的a
        }

        return ret;
    }
};

//等差数列划分 II - 子序列
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        int n = nums.size();

        //优化：快速判断在不在
        unordered_map<long long, vector<int>>hash;
        for(int i = 0; i < n; i++) hash[nums[i]].push_back(i);

        //创建dp表
        int ret = 0;
        vector<vector<int>> dp(n, vector<int>(n));
        //dp[i][j]表示，以i位置开始，j位置为结尾，所有子序列中等差数列的数量

        for(int j = 2; j < n; j++) //先固定j
        {
            for(int i = 1; i < j; i++)
            {
                long long a = (long long)2 * nums[i] - nums[j]; //可能存在整型溢出
                if(hash.count(a))
                {
                    for(auto k : hash[a])
                    {
                        if(k < i)
                            dp[i][j] += dp[k][i] + 1;
                    }
                }
                ret += dp[i][j]; //统计等差数列个数
            }
        }
        return ret;
    }
};

//摆动序列
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int left = 0, right = 0;
        int ret = 1;
        for(int i = 0; i < nums.size(); i++)
        {
            if(i + 1 < nums.size())
            {
                right = nums[i + 1] - nums[i];
            }
            if(right == 0) continue; // 不摆动的的情况
            if(left * right <= 0) ret++; //极值点
            left = right;
        }
        return ret;
    }
};

//最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n = nums.size();

        vector<int> ret; // 保存贪心解
        ret.push_back(nums[0]);

        for(int i = 1; i < n; i++)
        {
            if(ret.back() < nums[i]) //只要比当前最后一个位置大，说明可以是递增子序列
                ret.push_back(nums[i]);
            else // 否则二分找到某一个比它大的位置覆盖
            {
                //二分
                int left = 0, right = ret.size() - 1;
                while(left < right)
                {
                    int mid = (left + right) >> 1;
                    if(ret[mid] < nums[i]) left = mid + 1;
                    else right = mid;
                }
                ret[left] = nums[i];
            }
        }   
        
        return ret.size(); // 最终长度就存在这个数组中
    }
};

//最长回文子串
class Solution {
public:
    string longestPalindrome(string s) 
    {
        int n = s.size();
        
        //创建dp表
        vector<vector<bool>> dp(n, vector<bool>(n));
        int begin = 0, maxlen = 0;
        //填表
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = i; j < n; j++)
            {
                if(s[i] == s[j])
                {
                    if(i == j)
                        dp[i][j] = true;
                    else if(i + 1 == j)
                        dp[i][j] = true;
                    else if(i + 1 < j)
                        dp[i][j] = dp[i + 1][j - 1];
                }
                if(dp[i][j] == true)
                {
                    if(maxlen < j - i + 1)
                    {
                        maxlen = j - i + 1;
                        begin = i;
                    }
                }
            }
        }

        return s.substr(begin, maxlen);
    }
};

//分割回文串 IV
class Solution {
public:
    bool checkPartitioning(string s) 
    {
        int n =  s.size();

        vector<vector<bool>> dp(n, vector<bool>(n));

        //先动态规划预处理
        for(int i = n - 1; i >= 0; --i)    
        {
            for(int j = i; j < n; j++)
            {
                if(s[i] == s[j])
                {
                    if(i == j)
                        dp[i][j] = true;
                    else if(i + 1 == j)
                        dp[i][j] = true;
                    else if(i + 1 < j)
                        dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }
        //固定i，j暴力枚举
        for(int i = 1; i < n - 1; i++)
        {
            for(int j = i; j < n - 1; j++)
            {
                if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
                    return true;
            }
        }

        return false;
    }
};

//在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        //处理边界情况
        if(nums.size() == 0) return {-1, -1};   

        int begin = 0;
        int left = 0, right = nums.size() - 1;
        //先找左端点
        while(left < right) 
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        if(nums[left] != target)
            return {-1, -1};
        else 
            begin = left;

        //left不需要置0
        right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        if(nums[left] != target)
            return {-1, -1};
        else 
            return {begin, left};
    }
};

//分割回文串 II
class Solution {
public:
    int minCut(string s) 
    {
        int n = s.size();

        //预处理
        vector<vector<bool>>dp(n, vector<bool>(n));      
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = i; j < n; j++)
            {
                if(s[i] == s[j])
                {
                    if(i == j)
                        dp[i][j] = true;
                    else if(i + 1 == j)
                        dp[i][j] = true;
                    else if(i + 1 < j)
                        dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }

        vector<int>f(n, INT_MAX);  
        for(int i = 0; i < n; i++)
        {
            if(dp[0][i])
                f[i] = 0;
            else
            {
                for(int j = 1; j <= i; j++)
                {
                    if(dp[j][i])
                    {
                        f[i] = min(f[i], f[j - 1] + 1);
                    }
                }
            }
        }
        return f[n - 1];
    }
};

//你波兰表达式求值
class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {   
        unordered_map<string, function<int(int,int)>> CmdMap = {
            {"+", [](int x, int y){return x + y;}},
            {"-", [](int x, int y){return x - y;}},
            {"*", [](int x, int y){return x * y;}},
            {"/", [](int x, int y){return x / y;}}
            
        };

        stack<int> st;
        for(auto& str : tokens){
            if(CmdMap.count(str))
            {
                int right = st.top();
                st.pop();

                int left = st.top();
                st.pop();

                st.push(CmdMap[str](left, right));
            }
            else
                st.push(stoi(str));
        }
        return st.top();
    }
};

//最长回文子序列
class Solution {
public:
    int longestPalindromeSubseq(string s) 
    {
        int n = s.size();

        vector<vector<int>>dp(n, vector<int>(n));
        //dp[i][j]表示以[i, j]区间内的最长回文子序列的长度
        //因为边界情况下面会特殊处理 s[i] == s[j], 所以无需初始化

        //填表：从下往上填写每一行，从左往右填写每一列
        for(int i = n - 1; i >= 0; i--)
        {
            dp[i][i] = 1;
            for(int j = i + 1; j < n; j++)
            {
                if(s[i] == s[j])
                {
                    // else if(i + 1 == j)
                    //     dp[i][j] = 2;
                    // else if(i + 1 < j)
                    //如果是i + 1 < j 的情况 dp[i + 1][j - 1] = 0
                    //因为dp表我们只用对角线以上的部分
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                }
                else 
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 
            }
        }

        //返回0到n-1区间最长回文子序列的长度
        return dp[0][n - 1];
    }
};

//让字符串成为回文串的最少插入次数
class Solution {
public:
    int minInsertions(string s) 
    {
        int n = s.size();

        //创建dp表
        vector<vector<int>>dp(n, vector<int>(n));
        //dp[i][j]表示[i, j]区间内让字符串成为回文串的最少插入次数
        //无需初始化

        //填表，顺序为从下往上从左往右
        for(int i = n - 1; i >= 0; --i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
                else dp[i][j] = min((1 + dp[i][j - 1]),(1 + dp[i + 1][j]));
                //1 + dp[i][j - 1]，表示在左边 + 一个字符 让 s[i - 1] == s[j]
                //1 + dp[i + 1][j]，表示在右边 + 一个字符 让 s[i] == s[j + 1]
            }
        }
        //根据状态表示直接返回0到n-1区间的dp值
        return dp[0][n - 1];
    }
};

//递增的三元子序列
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> ret;//保存贪心解
        ret.push_back(nums[0]); //初始化

        for(int i = 1; i < n; i++)
        {
            if(nums[i] > ret.back())
                ret.push_back(nums[i]);
            else
            {
                //二分找到合适位置替换
                int left = 0, right = ret.size() - 1;
                while(left < right)
                {
                    int mid = (right + left) >> 1;
                    if(ret[mid] < nums[i]) left = mid + 1;
                    else right = mid;
                }
                ret[left] = nums[i];
            }
        }

        return ret.size() >= 3;
    }
};

// 最长公共子序列
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        int m = text1.size(), n = text2.size();

        //dp[i][j]表示s1的[0,i]区间和s2的[0, j]区间内所有子序列中，最长子序列的长度
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        //为了方便填表，多开了一行一列的空间
        //为了建立正确映射关系，在两个字符串开头都加一个占位符
        text1 = ' ' + text1;
        text2 = ' ' + text2;

        //填报：顺序自上往下、从左往右
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(text1[i] == text2[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else 
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);// 准确的说还有dp[i-1][j-1],但是dp[i-1][j-1]包含在这两个情况里           
            }
        } 

        //根据状态表示，返回最后一个位置
        return dp[m][n];      
    }
};

//最长连续递增序列
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) 
    {
        int i = 0, j = 1, ret = -1;

        while(j < nums.size())
        {
            if(nums[j] > nums[j - 1])
                j++;
            else
            {
                ret = max(ret, j - i);
                i = j; // 贪心
                j++;
            }
        }   
        ret = max(ret, j - i);
        return ret;
    }
};

//不相交的线
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) 
    {
        int n = nums1.size(), m = nums2.size();

        vector<vector<int>>dp(n + 1, vector<int>(m + 1));
        //dp[i][j]表示nums1[0,i]和nums2[0,j]的最大连线数

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else 
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
};

//买卖股票的最佳时机
class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int prevMin = INT_MAX, ret = 0;
        for(int i = 0; i < prices.size(); i++)
        {
            prevMin = min(prevMin, prices[i]);
            ret = max(prices[i] - prevMin, ret);
        }   
        return ret;
    }
};

//不同的子序列
class Solution {
public:
    int numDistinct(string s, string t) 
    {
        int n = s.size(), m = t.size();

        //创建dp表
        //避免溢出，用double存储
        vector<vector<double>>dp(m + 1, vector<double>(n + 1));
        //dp[i][j]表示s字符串的[0, j]区间内的所有子序列中，有多少个t字符串[0, i]区间内的子串

        //初始化
        for(int j = 0; j <= n; j++) dp[0][j] = 1;

        //填表：从上到下，从左到右
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] += dp[i][j - 1];

                if(t[i - 1] == s[j - 1])
                    dp[i][j] += dp[i - 1][j - 1];
            }
        }

        return dp[m][n];
    }
};

//通配符匹配
class Solution {
public:
    bool isMatch(string s, string p) 
    {
        int m = s.size(), n = p.size();

        //创建dp表， 多创建一行一列的位置避免越界的情况
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        //dp[i][j]表示p字符串的[0, j]区间的子数组 与 s字符串的[0, i]区间的子数组是否匹配

        //初始化——第0行表示s串为"",p[i] == '*' 的情况
        dp[0][0] = true;
        bool flag = true;
        for(int i = 1; i <= n; i++)
        {
            if(flag == true && p[i - 1] == '*')
                dp[0][i] = true;
            else 
                break;
        }

        //填表——自上往下，从左往右的顺序填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(p[j - 1] == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j - 1] == '*')
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                else if(p[j - 1] != '?' && p[j - 1] != '*')
                    dp[i][j] = (s[i - 1] == p[j - 1]) && dp[i - 1][j - 1];
            }
        }

        //返回结果——返回dp表的最后一个元素
        return dp[m][n]; 
    }
};

//快排复习
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(nullptr)); // 种一棵随机数种子
        qsort(nums, 0, nums.size() - 1);
        return nums;    
    }

    void qsort(vector<int>& nums, int l, int r)
    {
        //处理边界情况
        if(l >= r) 
            return;

        //partion
        int key = getRand(nums, l, r); // 随机选key
        int i = l, left = l - 1, right = r + 1;
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }

        // [l, left] [left + 1, right - 1] [right, r]
        qsort(nums, l, left);
        qsort(nums, right, r);

    }

    int getRand(vector<int>& nums, int l, int r)
    {
        return nums[l + (rand() % (r - l + 1))]; // 需要注意 + l
    }
};

//正则表达式
class Solution {
public:
    bool isMatch(string s, string p) 
    {
        int m = s.size(), n = p.size();

        //创建dp表
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        //dp[i][j]表示p字符串[0, j]区间子串能否匹配字符串[0, i]区间子串

        //初始化——s为空串，p只要从第2给位置开始，每隔一个位置为* 就为true （_*能够匹配空串）
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2)
        {
            if(p[j - 1] == '*')
                dp[0][j] = true;
            else 
                break;
            
        }

        //填表——顺序从上往下，从左往右
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(p[j - 1] == '*')
                    dp[i][j] = dp[i][j - 2] || ( p[j - 2] == '.' || p[j - 2] == s[i - 1] ) && dp[i - 1][j];
                else
                    dp[i][j] = ((s[i - 1] == p[j - 1] )|| (p[j - 1] == '.')) && dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

//交错字符串
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        int n = s1.size(), m = s2.size();
        //处理边界情况，n+m != s3.size()说明没有必要研究直接返回false
        if(m + n != s3.size()) return false;
        //创建dp表
        vector<vector<bool>>dp(n + 1, vector<bool>(m + 1));
        //dp[i][j]表示s1[1, i]区间字符串 与 s2[1, j]区间字符串
        //是否可以拼接出s3[1, i + j]区间字符串    

        //初始化——先预处理s1、s2、s3
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        s3 = ' ' + s3;
        dp[0][0] = true; // s1为空串、s2为空串、s3为空串

        //处理s1为空时情况，当s2和s3第一次不相等就为false
        for(int i = 1; i <= m; i++)
        {
            if(s2[i] == s3[i])
                dp[0][i] = true;
            else 
                break;
        }

        //处理s2为空时情况，当s1和s3第一次不相等就为false
        for(int i = 1; i <= n; i++)
        {
            if(s1[i] == s3[i])
                dp[i][0] = true;
            else 
                break;
        }

        // 填表
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(s1[i] == s3[i + j] && dp[i - 1][j] == true)
                    dp[i][j] = true;
                else if(s2[j] == s3[i + j] && dp[i][j - 1] == true)
                    dp[i][j] = true;
            }
        }

        //返回结果
        return dp[n][m];
    }
};

//归并排序
class Solution {
    vector<int> tmp; // 用于归并
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergeSort(vector<int>& nums, int left, int right)
    {
        //处理边界情况
        if(left >= right) return;

        //计算中间节点
        int mid = (left + right) >> 1;

        //递归
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1 , right);

        //归并逻辑
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        
        //未归并直接尾插到tmp中
        while(cur1 <= mid) 
            tmp[i++] = nums[cur1++];

        while(cur2 <= right) 
            tmp[i++] = nums[cur2++]; 

        for(int i = left; i <= right; i++)
            nums[i] = tmp[i - left];
    }
};

//归并非递归
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        int n = nums.size();    
        vector<int> tmp(n);

        int gap = 1;
        while(gap < n)
        {
            for(int j = 0; j < n; j += 2 * gap)
            {
                int begin1 = j, end1 = j + gap - 1;
                int begin2 = j + gap, end2 = j + 2 * gap - 1;
                
                int i = j;

                //考虑越界情况
                if(end1 >= n)
                {
                    end1 = n - 1;
                    begin2 = n;
                    end2 = n - 1;
                }
                else if(begin2 >= n)
                {
                    begin2 = n;
                    end2 = n - 1;
                }
                else if(end2 >= n)
                {
                    end2 = n - 1;
                }
                
                //归并逻辑
                while(begin1 <= end1 && begin2 <= end2)
                    tmp[i++] = nums[begin1] <= nums[begin2] ? nums[begin1++] : nums[begin2++];

                while(begin1 <= end1) 
                    tmp[i++] = nums[begin1++];

                while(begin2 <= end2) 
                    tmp[i++] = nums[begin2++];

            }
            gap *= 2;
            //将tmp的内容拷贝给nums
            nums.clear();
            for(auto e : tmp)
                nums.push_back(e);
        }

        return nums;
    }   
};

//两个字符串的最小ASCII删除和
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) 
    {
        int n = s1.size(), m = s2.size();

        //创建dp表
        vector<vector<int>>dp(n + 1, vector<int>(m + 1));
        //采用正难则反的思想，求两个字符串所有公共子序列的最大ASCII和
        //dp[i][j]表示s1[0, i]区间内以及s2[0, j]区间内所有子序列的公共子序列最大ASCII和

        //填表——从上往下，从左往右
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(s1[i - 1] == s2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + s1[i - 1];
                else 
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        //dp[n][m]内为s1[0, n] 和 s2[0, m]的最大公共子序列的和
        //要求返回公共子序列最小和，所以统计两个字符串的ASCII和减去2 * dp[n][m]即可。
        int sum = 0;
        for(char ch : s1)
            sum += ch;

        for(char ch : s2)
            sum += ch;

        return sum - (2 * dp[n][m]);
    }
};

//最长重复子数组
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) 
    {
        int n = nums1.size(), m = nums2.size();

        //创建dp表
        vector<vector<int>>dp(n + 1, vector<int>(m + 1));
        //dp[i][j] 表示nums1中以i位置为结尾的所有子数组和nums2中以j位置为结尾的所有子数组中，最长重复子数组的长度
        //无需特殊初始化
        //填表
        int ret = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(nums1[i - 1] == nums2[j - 1])//根据j的位置分情况讨论
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(dp[i][j], ret);
                }
                else 
                {
                    dp[i][j] = 0;
                }
            }
        }
        //返回dp表最大值
        return ret;
    }
};

//K 次取反后最大化的数组和
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) 
    {
        int m = nums.size();
        int n = 0; // 负数的个数
        for(int i = 0; i < m; i++)
        {
            if(nums[i] < 0) n++;
        }   

        if(n >= k) // k <= 负数个数
        {
            for(int i = k; i > 0; i--)
            {
                int min = 0;
                for(int i = 1; i < m; i++)
                {
                    if(nums[i] < nums[min])
                        min = i;
                }
                nums[min] = -nums[min];
            }
        }
        else // k > 负数个数
        {
            int count = k;
            for(int i = 0; i < m; i++)
            {
                if(nums[i] < 0)
                {
                    nums[i] = -nums[i];
                    count--;
                }
            }

            if(count % 2 == 1)
            {
                int min = 0;
                for(int i = 1; i < m; i++)
                {
                    if(nums[min] > nums[i])
                        min = i;
                }
                nums[min] = -nums[min];
            }
        }

        int ret = 0;
        for(int e: nums)
            ret += e;

        return ret;
    }
};

//01背包
#include <iostream>
#include <string.h>
using namespace std;

const int N = 1010;

int dp[N][N]; // 创建dp表
int n, V, v[N], w[N];

int main() 
{
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    // 情况一
    // dp[i][j]表示从前i个物品中，总体积不超过V的所有选法中，挑出来价值最高
    //无需初始化
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j]; // 不选第i个物品的情况
            if(j >= v[i])// j - v[i] >= 0, 即体积还有余量装下i物品
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }

    cout << dp[n][V] << endl;

    //情况二
    //dp[i][j]表示从前i个物品中，总体积等于V的所有选法中，挑出来价值最高
    //需要将第一行第二列到第V列的值初始化为-1，将体积为0的物品凑成V体积容量情况不存在
    memset(dp, 0, sizeof(dp)); // 清空dp表
    for(int j = 1; j<= V; j++) dp[0][j] = -1;

    //填表
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j]; // 不选第i个物品的情况
            if(j >= v[i] && dp[i - 1][j - v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    //返回结果，需要考虑无法装满的情况
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    return 0;
}

//01背包——滚动数组优化
#include <iostream>
#include <string.h>
using namespace std;

const int N = 1010;

int dp[N]; // 创建dp表
int n, V, v[N], w[N];

int main() 
{
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    // 情况一
    // dp[i][j]表示从前i个物品中，总体积不超过V的所有选法中，挑出来价值最高
    //无需初始化
    for(int i = 1; i <= n; i++)
    {
        for(int j = V; j >= v[i]; j--) //修改便利顺序
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    cout << dp[V] << endl;

    //情况二
    //dp[i][j]表示从前i个物品中，总体积等于V的所有选法中，挑出来价值最高
    //需要将第一行第二列到第V列的值初始化为-1，将体积为0的物品凑成V体积容量情况不存在
    memset(dp, 0, sizeof(dp)); // 清空dp表
    for(int j = 1; j<= V; j++) dp[j] = -1;

    //填表
    for(int i = 1; i <= n; i++)
    {
        for(int j = V; j >= v[i]; j--)
        {
            if(dp[j - v[i]] != -1)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    //返回结果，需要考虑无法装满的情况
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

    return 0;
}

//分割等和子集
// class Solution {
// public:
//     bool canPartition(vector<int>& nums) 
//     {
//         //将问题转化为在数组中求某些数的和为nums的和 / 2的情况存不存在
//         int n = nums.size(), sum = 0;
//         for(int i: nums)
//             sum += i;
        
//         if(sum % 2 == 1) return false; // 处理边界情况

//         //创建dp表
//         vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1));
//         //dp[i][j]表示从前i个数中选，所有选法中，能否凑出和为j的情况        
        
//         //初始化，将第0列初始化为true，因为只要不选nums的数都能凑出和为0的情况  
//         for(int i = 0; i <= n; i++)
//         {
//             dp[i][0] = true;
//         }

//         for(int i = 1; i <= n; i++)
//         {
//             for(int j = 1; j <= sum / 2; j++)
//             {
//                 dp[i][j] = dp[i - 1][j];
//                 if(j >= nums[i - 1])
//                     dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
//             }
//         }

//         return dp[n][sum / 2];
//     }
// };

//目标和
class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        //将问题转化为在数组中求某些数的和为nums的和 / 2的情况存不存在
        int n = nums.size(), sum = 0;
        for(int i: nums)
            sum += i;
        
        if(sum % 2 == 1) return false; // 处理边界情况

        //创建dp表
        vector<bool>dp(sum + 1);
        //dp[i][j]表示从前i个数中选，所有选法中，能否凑出和为j的情况        
        
        //初始化，将第0列初始化为true，因为只要不选nums的数都能凑出和为0的情况  
        dp[0] = true;

        for(int i = 1; i <= n; i++)
        {
            for(int j = sum; j >= nums[i - 1]; j--)
                dp[j] = dp[j] || dp[j - nums[i - 1]];
        }

        return dp[sum / 2];
    }
};

// class Solution {
// public:
//     int findTargetSumWays(vector<int>& nums, int target) 
//     {
//         //将问题转化成，在nums中选一些数，让这些数的和等与(nums的和 + target) / 2，一共有多少种选法？
//         int n = nums.size();
//         int sum = 0;
//         for(int x : nums)
//             sum += x;

//         int a = (sum + target) / 2;
         
//         //处理边界情况
//         if(a < 0 || (sum + target) % 2) 
//             return 0;

//         // 创建dp表
//         vector<vector<int>> dp(n + 1, vector<int>(a + 1));

//         //初始化
//         dp[0][0] = 1;
//         //而第0列因为状态转移方程的中选i时，取dp[i - 1][j - nums[i]]，所以无需初始化

//         //填表
//         for(int i = 1; i <= n; i++)
//         {
//             for(int j = 0; j <= a; j++)// 需要从0开始初始化，因为第0列的数需要依赖上一列数的值
//             {
//                 if(j >= nums[i - 1])
//                     dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
//                 else 
//                     dp[i][j] = dp[i - 1][j];
//             }
//         }

//         return dp[n][a];
//     }
// };

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        //将问题转化成，在nums中选一些数，让这些数的和等与(nums的和 + target) / 2，一共有多少种选法？
        int n = nums.size();
        int sum = 0;
        for(int x : nums)
            sum += x;

        int a = (sum + target) / 2;
         
        //处理边界情况
        if(a < 0 || (sum + target) % 2) 
            return 0;

        // 创建dp表
        vector<int> dp(a + 1);

        //初始化
        dp[0] = 1;

        //填表
        for(int i = 1; i <= n; i++)
            for(int j = a; j >= nums[i - 1]; j--)
            {
                dp[j] += dp[j - nums[i - 1]];
            }

        return dp[a];
    }
};

//最后一块石头的重量||
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) 
    {
        int sum = 0;
        int n = stones.size();

        for(int x : stones)
            sum += x;

        int m = sum / 2;

        //将问题转化成从stones中挑选出一些数，使它们的和为sum / 2
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        //dp[i][j]表示：从前i个数中选择一些数，它们的和不超过j，此时的最大和
        //初始化——无需初始化

        //填表顺序为：从上往下填表
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                if(j >= stones[i - 1])
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
                else 
                    dp[i][j] = dp[i - 1][j];
            }

        //返回值
        return sum - 2 * dp[n][m];
    }

};

//完全背包
// #include <iostream>
// #include <string.h>
// using namespace std;

// const int N = 1010;

// int dp[N][N]; // 创建dp表
// int n, V, v[N], w[N];

// int main() 
// {
//     cin >> n >> V;
//     for(int i = 1; i <= n; i++)
//         cin >> v[i] >> w[i];

//     // 情况一
//     // dp[i][j]表示从前i个物品中，总体积不超过V的所有选法中，挑出来价值最高
//     //无需初始化
//     for(int i = 1; i <= n; i++)
//     {
//         for(int j = 0; j <= V; j++)
//         {
//             dp[i][j] = dp[i-1][j]; // 不选第i个物品的情况
//             if(j >= v[i])// j - v[i] >= 0, 即体积还有余量装下i物品
//                 dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
//         }
//     }

//     cout << dp[n][V] << endl;

//     //情况二
//     //dp[i][j]表示从前i个物品中，总体积等于V的所有选法中，挑出来价值最高
//     //需要将第一行第二列到第V列的值初始化为-1，将体积为0的物品凑成V体积容量情况不存在
//     memset(dp, 0, sizeof(dp)); // 清空dp表
//     for(int j = 1; j<= V; j++) dp[0][j] = -1;

//     //填表
//     for(int i = 1; i <= n; i++)
//     {
//         for(int j = 0; j <= V; j++)
//         {
//             dp[i][j] = dp[i-1][j]; // 不选第i个物品的情况
//             if(j >= v[i] && dp[i][j - v[i]] != -1)
//                 dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);

//         }
//     }
//     //返回结果，需要考虑无法装满的情况
//     cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

//     return 0;
// }

#include <iostream>
#include <string.h>
using namespace std;

const int N = 1010;

int dp[N]; // 创建dp表
int n, V, v[N], w[N];

int main() 
{
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    // 情况一
    // dp[i][j]表示从前i个物品中，总体积不超过V的所有选法中，挑出来价值最高
    //无需初始化
    for(int i = 1; i <= n; i++)
    {
        for(int j = v[i]; j <= V; j++)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    cout << dp[V] << endl;

    //情况二
    //dp[i][j]表示从前i个物品中，总体积等于V的所有选法中，挑出来价值最高
    //需要将第一行第二列到第V列的值初始化为-1，将体积为0的物品凑成V体积容量情况不存在
    memset(dp, 0, sizeof(dp)); // 清空dp表
    for(int j = 1; j<= V; j++) dp[j] = -1;

    //填表
    for(int i = 1; i <= n; i++)
    {
        for(int j = v[i]; j <= V; j++) // j >= v[i] 所以从v[i]开始
        {
            if(dp[j - v[i]] != -1)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

        }
    }
    //返回结果，需要考虑无法装满的情况
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

    return 0;
}

//零钱兑换
class Solution {
public:
    // int coinChange(vector<int>& coins, int amount) 
    // {
    //     int n = coins.size();

    //     //创建dp表
    //     vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
    //     //dp[i][j] 表示：在前i个硬币中选，总和恰好等于j，所有选法中，使用的硬币数最少

    //     //初始化
    //     int INF = 0x3f3f3f3f;
    //     for(int j = 1; j <= amount; j++) 
    //         dp[0][j] = INF; // 该状态不存在
        
    //     //填表：顺序从左往右，从上往下
    //     for(int i = 1; i <= n; i++)
    //     {
    //         for(int j = 0; j <= amount; j++)
    //         {
    //             dp[i][j] = dp[i - 1][j]; // 不选的情况
    //             if(j >= coins[i - 1]) //选的情况
    //                 dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
    //         }
    //     }

    //     return dp[n][amount] >= INF ? -1 : dp[n][amount];
    // }

    //滚动数组优化
    int coinChange(vector<int>& coins, int amount) 
    {
        int n = coins.size();

        //创建dp表
        vector<int> dp(amount + 1);               
        //dp[i][j] 表示：在前i个硬币中选，总和恰好等于j，所有选法中，使用的硬币数最少

        //初始化
        int INF = 0x3f3f3f3f;
        for(int j = 1; j <= amount; j++) 
            dp[j] = INF; // 该状态不存在
        
        //填表：顺序从左往右，从上往下
        for(int i = 1; i <= n; i++)
        {
            for(int j = coins[i - 1]; j <= amount; j++)
            {
                dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }

        return dp[amount] >= INF ? -1 : dp[amount];
    }
};

//零钱问题II
// class Solution {
// public:
//     int change(int amount, vector<int>& coins) 
//     {
//         int n = coins.size();

//         //创建dp表
//         vector<double> dp(amount + 1);
//         //dp[i][j]表示从前i个硬币中选，总和恰好等于j的所有选法的数量

//         //初始化
//         dp[0] = 1;

//         //填表 从上往下，从左往右
//         for(int i = 0; i < n ; i++)
//         {
//             for(int j = coins[i]; j <= amount; j++)
//             {
//                 dp[j] += dp[j - coins[i]];
//             }
//         }       

//         return dp[amount];
//     }
// };

class Solution {
public:
    int change(int amount, vector<int>& coins) 
    {
        int n = coins.size();

        //创建dp表
        vector<vector<double>> dp(n + 1, vector<double>(amount + 1));
        //dp[i][j]表示从前i个硬币中选，总和恰好等于j的所有选法的数量

        //初始化
        dp[0][0] = 1;

        //填表 从上往下，从左往右
        for(int i = 1; i <= n ; i++)
        {
            for(int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1])
                    dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }       

        return dp[n][amount];
    }
};

//增减字符串匹配
class Solution {
public:
    vector<int> diStringMatch(string s) 
    {
        //若当前字符为‘I’就选则下标数组中最小的
        //若当前字符为‘D’就选则下标数组中最大的

        //初始化
        int n = s.size();
        vector<int> ret;
        int left = 0, right = n; 
        for(char ch : s)
        {
            if(ch == 'I')
                ret.push_back(left++);
            else 
                ret.push_back(right--);
        }

        //还需要处理剩下的那一个数,此时left和right重叠
        ret.push_back(left);
        return ret;
    }
};

//完全平方和
// class Solution {
// public:
//     int numSquares(int n) 
//     {
//         int m = sqrt(n); // 取n的平方根
        
//         //创建dp表
//         vector<vector<int>> dp(m + 1, vector<int>(n +1 ));
//         //状态表示：dp[i][j]表示从前i个完全平方和中选，总和恰好等于j，所有选法中，完全平方数的最少数量。

//         //初始化，将第一行的第1列到第n列初始化为INF
//         int INF = 0x3f3f3f3f; // 描述不存在的状态，方便取min
//         for(int j = 1;j <= n; j++)
//             dp[0][j] = INF;


//         for(int i = 1; i <= m; i++)
//             for(int j = 0; j <= n; j++)
//             {
//                 dp[i][j] = dp[i - 1][j]; // 不选i的情况
    
//                 if(j >= i * i)//选i的情况
//                 {
//                     dp[i][j] = min(dp[i][j], dp[i][j - i*i] + 1);
//                 }
//             }
        
//         return dp[m][n];
//     }
// };

class Solution {
public:
    int numSquares(int n) 
    {
        int m = sqrt(n); // 取n的平方根
        
        //创建dp表
        vector<int>dp(n + 1, 0x3f3f3f3f);
        //状态表示：dp[i][j]表示从前i个完全平方和中选，总和恰好等于j，所有选法中，完全平方数的最少数量。

        //初始化，将第一行的第1列到第n列初始化为INF
        dp[0]= 0;

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                if(j >= i * i)//选i的情况
                {
                    dp[j] = min(dp[j], dp[j - i*i] + 1);
                }
            }
        
        return dp[n];
    }
};

// class Solution {
// public:
//     int findMaxForm(vector<string>& strs, int m, int n) 
//     {
//         int len = strs.size();

//         //创建dp表
//         vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
//         //dp[i][j][k]表示：从前i个字符串中选，字符 0 个数小于等于m， 字符 1个数小于等于n的情况下，最大子集长度。

//         //无需初始化

//         //填表——i从小往大

//         for(int i = 1; i <= len; i++)
//         {
//             //统计 '0' 和 '1'的个数
//             int a = 0, b = 0; 
//             for(char ch : strs[i - 1])
//             {   
//                 if(ch == '0')
//                     a++;
//                 else 
//                     b++;
//             }


//             for(int j = 0; j <= m; j++)
//             {

//                 for(int k = 0; k <= n; k++)
//                 {
//                     //不选
//                     dp[i][j][k] = dp[i - 1][j][k];
//                     if(j >= a && k >= b) // 选
//                     {
//                         dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
//                     }

//                 }
//             }
//         }

//         //返回值
//         return dp[len][m][n];
//     }
// };

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) 
    {
        int len = strs.size();

        //创建dp表
        vector<vector<int>>dp(m + 1, vector<int>(n + 1));
        //dp[i][j][k]表示：从前i个字符串中选，字符 0 个数小于等于m， 字符 1个数小于等于n的情况下，最大子集长度。

        //无需初始化

        //填表——i从小往大

        for(int i = 1; i <= len; i++)
        {
            //统计 '0' 和 '1'的个数
            int a = 0, b = 0; 
            for(char ch : strs[i - 1])
            {   
                if(ch == '0')
                    a++;
                else 
                    b++;
            }

            //滚动数组优化，需要从后往前遍历
            for(int j = m; j >= a; j--)
            {

                for(int k = n; k >= b; k--)
                    dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);
            }
        }

        //返回值
        return dp[m][n];
    }
};

//盈利计划
// class Solution {
// public:
//     int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) 
//     {
//         int len = group.size();
//         //创建dp表
//         //dp[i][j][k]表示：从前i个计划中选，总人数不超过j，总利润至少为k，一共多少种选法
//         vector<vector<vector<int>>>dp(len+1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
//         int flag = 1e9 + 7;
//         //初始化
//         for(int j = 0; j <= n; j++)
//             dp[0][j][0] = 1; // 

class Solution {
public:
    int f(int num, int target)
    {
        //处理边界情况
        if(num == 1)
            return 0;
        //子问题
        int x = f(num - 1, target);
        return (target + x) % num;
    }
    int iceBreakingGame(int num, int target) 
    {
        return f(num, target);
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* cur = head, *last = nullptr;
        while(cur)
        {
            ListNode* next = cur->next; 
            cur->next = last;
            last = cur;
            cur = next;
        }

        return last;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    vector<vector<int>> ret;
    vector<int> path;

    void dfs(TreeNode* root, int targetSum)
    {
        //采用前序遍历的的思想，暴力枚举每一个路径，判断是否满足条件

        //处理边界情况
        if(root == nullptr)
            return;

        path.push_back(root->val);
        targetSum -= root->val;
        if(root->left == nullptr && root->right == nullptr && targetSum == 0)
            ret.push_back(path);
        
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);

        path.pop_back();
        
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) 
    {
        dfs(root,targetSum);
        return ret;
    }
};

class Solution {
public:
    vector<int> grayCode(int n) 
    {
        vector<int>ret;
        ret.reserve(1 << n);
        ret.push_back(0); // 第一位都是0

        for(int i = 1; i <= n; i++)
        {
            int m = ret.size();
            for(int j = m - 1; j >= 0; j--)
            {
                ret.push_back(ret[j] | (1 << (i - 1)));
            }
        }
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        vector<pair<TreeNode*,unsigned int>> q; // 模拟队列
        q.push_back({root, 1});
        unsigned int ret = 0;
        while(q.size())
        {
            //更新结果
            //根据层序遍历的性子将队尾的值减去队头的值就是树的宽度
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);
            
            vector<pair<TreeNode*,unsigned int>> tmp; // 保存一层的结果

            for(auto &[x, y] : q)
            {
                if(x->left) tmp.push_back({x->left, y * 2});
                if(x->right) tmp.push_back({x->right, y * 2 + 1});
            }
            q = tmp;//迭代条件，当遍历完最后一层时，tmp为空，跳出循环。
        }
        return ret;
    }
};

//图书管理||
class CQueue {
public:
    stack<int> _pushStack;
    stack<int> _popStack;
    CQueue() 
    {
    }
    
    void appendTail(int value) {
        _pushStack.push(value);
    }
    
    int deleteHead() 
    {
        if(_popStack.empty())
        {
            //将_pushStack数据依次插入_popStack
            if(!_pushStack.empty())
            {
                while(!_pushStack.empty())
                {
                    int t = _pushStack.top();
                    _pushStack.pop();
                    _popStack.push(t);
                }

                int ret = _popStack.top();
                _popStack.pop();
                return ret;
            }
            else
            {
                return -1;
            }
        } 
        else
        {
            int ret = _popStack.top();
            _popStack.pop();
            return ret;
        }   
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */


 //二叉树的锯齿状层序遍历
 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        //处理边界情况
        if(root == nullptr) return ret;
        q.push(root);
        int flag = 1;

        while(q.size())
        {
            //层序遍历逻辑
            vector<int> v;
            int n = q.size();
            for(int i = 0; i < n; i++)
            {
                TreeNode* a = q.front();
                q.pop();
                if(a->left) q.push(a->left);
                if(a->right) q.push(a->right);
                v.push_back(a->val);
            }

            //控制锯齿形
            if(flag == 1)
            {
                ret.push_back(v);
                v.clear();
                flag = 0;
            }
            else
            {
                reverse(v.begin(), v.end());
                ret.push_back(v);
                v.clear();
                flag = 1;
            }
        }
        return ret;
    }
};

class MyCircularQueue {
public:
    vector<int> rq;
    int f = 0, r = 0,c = 0;    

    MyCircularQueue(int k) 
    {
        rq.reserve(k + 1);
        f = 0;
        r = 0;
        c = k + 1;
    }
    
    bool enQueue(int value) 
    {   
        if(isFull()) return false;
        rq[r] = value;
        r = (r + 1) % c;
        return true;
    }
    
    bool deQueue() 
    {
        if(isEmpty()) return false;

        f = (f + 1) % c;
        return true;
    }
    
    int Front() 
    {
        if(isEmpty()) return -1;
        return rq[f];
    }
    
    int Rear() {
        if(isEmpty()) return -1;
        return rq[(r - 1 + c) % c] ;
    }
    
    bool isEmpty() 
    {
        return r == f;    
    }
    
    bool isFull() 
    {
        return f == ((r + 1) % c);
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */


class Solution {
public:
    char dismantlingAction(string arr) 
    {
        char ret = ' ';
        if(arr.size() == 0) return ret;
        int hash[26] = {0};
        for(char ch : arr)
            hash[ch - 'a']++;
        for(char ch : arr)
        {
            if(hash[ch - 'a'] == 1)
            return ch;
        }
        return ret;
    }
};

class AnimalShelf {
public:
    queue<int> cats, dogs;

    AnimalShelf() {}

    void enqueue(vector<int> animal) {
        if (animal[1] == 0)
            cats.push(animal[0]);
        else
            dogs.push(animal[0]);
    }

    vector<int> dequeueAny() {
        if (cats.size() == 0 && dogs.size() == 0)
            return {-1, -1};

        if (cats.empty()) {
            int ret = dogs.front();
            dogs.pop();
            return {ret, 1};
        }
        else if (dogs.empty()) {
            int ret = cats.front();
            cats.pop();
            return {ret, 0};
        }
        else
        {
            int retm = cats.front();
            int retd = dogs.front();
            if(retm > retd)
            {
                dogs.pop();
                return {retd, 1};
            }
            else
            {
                cats.pop();
                return {retm, 0};
            }
        }

        return {-1, -1};
    }

    vector<int> dequeueDog() {
        if (dogs.empty())
            return {-1, -1};
        int ret = dogs.front();
        dogs.pop();
        return {ret, 1};
    }

    vector<int> dequeueCat() {
        if (cats.empty())
            return {-1, -1};
        int ret = cats.front();
        cats.pop();
        return {ret, 0};
    }
};

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf* obj = new AnimalShelf();
 * obj->enqueue(animal);
 * vector<int> param_2 = obj->dequeueAny();
 * vector<int> param_3 = obj->dequeueDog();
 * vector<int> param_4 = obj->dequeueCat();
 */

 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        vector<int> ret;
        queue<TreeNode*> q;

        //处理边界情况
        if(root == nullptr) 
            return ret;

        q.push(root);

        while(q.size())
        {
            vector<int> tmp;
            int n = q.size();
            for(int i = 0; i < n;i++)
            {
                TreeNode* ro = q.front();
                tmp.push_back(ro->val);
                
                q.pop();
                if(ro->left)
                    q.push(ro->left);
                if(ro->right)
                    q.push(ro->right);
                
            }
            if(!tmp.empty())
                ret.push_back(tmp[tmp.size() - 1]);
            tmp.clear();
        }
        return ret;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>> ret;
        //处理边界情况
        if(root == nullptr)
            return ret;

        //层序遍历
        queue<Node*> q;
        q.push(root);
        while(q.size())
        {
            //单层遍历
            vector<int> tmp;
            int n = q.size();
            for(int i = 0; i < n; i++)
            {
                Node* cur = q.front();
                q.pop();
                tmp.push_back(cur->val);

                for(int i = 0; i < cur->children.size(); i++)
                {
                    q.push(cur->children[i]);
                }
            }
            ret.push_back(tmp);
            tmp.clear();
        }
        return ret;
    }
};

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        //采用大根堆的形式

        //处理边界情况
        if(stones.size() == 1)
            return stones[0];

        priority_queue<int> pq;

        for(int a : stones)
        {
            pq.push(a);
        }

        while(pq.size() > 1)
        {
            int top1 = pq.top();
            pq.pop();
            int top2 = pq.top();
            pq.pop();

            int newtop = top1 - top2;
            if(newtop >= 1)
                pq.push(newtop);
        }

        if(pq.size() == 0)
            return 0;
        else
            return pq.top();
    }
};

class Solution {
public:
    string removeKdigits(string num, int k) 
    {
        //采用栈来进行
        vector<char> stack;
        for(char dig : num)
        {
            //加入当前元素比栈顶元素小，那就让栈顶元素出栈
            while(stack.size() > 0 && stack.back() > dig && k != 0)
            {
                stack.pop_back();
                k--;
            }
            stack.push_back(dig);
        } 

        //栈的长度大于 num.size() - k
        while(k--)
        {
            stack.pop_back();
        }

        string ret = "";
        bool flag = true; // 判断是否有前导零
        for(char dig : stack)
        {
            if(dig == '0' && flag)//有前导零
            {
                continue;
            }
            flag = false;
            ret.push_back(dig);
        }

        return ret == "" ? "0" : ret;
    }
};

//LRU缓存
struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    //默认构造
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) 
    {}
    //带参构造
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) 
    {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache; //快速定位节点
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        //不存在key就返回-1
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        // head --> node --> head->next
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        // node->prev --> node -->  node->next
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

//无法吃午餐的学生数量
class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) 
    {
        //先统计所有学生的需求
        int sum_1 = 0;
        int sum_0 = 0;
        for(int a : students)  
        {
            if(a == 0)
                sum_0++;
            else 
                sum_1++;
        }  

        //直接遍历三明治数组，通过学生需求依次拿走三明治，若某一种的需求被满足就结束遍历
        for(int i = 0; i < sandwiches.size(); i++)
        {
            if(sandwiches[i] == 0 && sum_0)
            {
                sum_0--;
            }
            else if(sandwiches[i] == 1 && sum_1)
            {
                sum_1--;
            }
            else if(sandwiches[i] == 1 && !sum_1)
            {
                break;
            }            
            else if(sandwiches[i] == 0 && !sum_0)
            {
                break;
            }
            
        }
        return sum_0 + sum_1;
    }
};

//最近的请求次数

class RecentCounter 
{
public:
    vector<int> RC;

    RecentCounter() 
    {
    }
    
    int ping(int t) 
    {
        RC.push_back(t);
        return RC.size() - (lower_bound(RC.begin(), RC.end(), t - 3000) - RC.begin());
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

  class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;

    void dfs(int pos, int last, vector<int>& nums)
    {
        //递归出口
        if(pos == nums.size())
        {
            //递增子序列至少为2个元素构成
            if(tmp.size() >= 2)
            {
                ret.push_back(tmp);
            }
            return;
        }

        if(nums[pos] >= last){
            tmp.push_back(nums[pos]);
            dfs(pos + 1, nums[pos], nums);
            //剪枝
            tmp.pop_back();
        }
        
        if(nums[pos] != last)
        {
            dfs(pos + 1, last, nums);
        }

    }

    vector<vector<int>> findSubsequences(vector<int>& nums) 
    {
        dfs(0, INT_MIN, nums);
        return ret;
    }
};

class Solution {
public:
    int climbStairs(int n) 
    {
        //dp

        //处理边界情况
        if(n == 1)
            return 1;
        
        //滚动数组优化
        int p = 1;
        int q = 1;
        int k = 0;

        for(int i = 2; i <= n; i++)
        {
            k = p + q;
            p = q;
            q = k;
        }

        return k;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> ret;
    void dfs(TreeNode* root)
    {   
        if(root == nullptr)
        {
            return;
        }

        ret.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }

    vector<int> preorderTraversal(TreeNode* root) 
    {
        dfs(root);
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur = nullptr;

        //处理边界情况
        if(root)
            cur = root;  

        while(cur || !st.empty())
        {
            //访问根节点以及让左子树节点依次入栈
            while(cur)
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            //依次处理右子树部分
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;
        }
        return ret;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */

    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool visi[210][210] = {false};

    void dfs(vector<vector<char> >& grid, int i, int j)
    {
        visi[i][j] = true;

        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !visi[x][y])
            {
                dfs(grid, x, y);
            }
        }
    }

    int solve(vector<vector<char> >& grid) 
    {
        int ret = 0;
        m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == '1' && !visi[i][j])
                {
                    ret++;
                    dfs(grid, i, j);
                }
            }   
        return ret;     
    }
};

//扑克牌顺子
#include <cmath>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return bool布尔型
     */
    bool IsContinuous(vector<int>& numbers) 
    {
        sort(numbers.begin(), numbers.end());
        int cnt = 0;
        int i = 0;
        while(numbers[i] == 0) 
        {
            i++;
            cnt++;
        }
        int gap = 0;
        for(; i < numbers.size() - 1; i++)
        {
            if(numbers[i] == numbers[i + 1]) //相同牌
                return false;
            gap += numbers[i + 1] - numbers[i] - 1; //两个数之间的间距
        }
        if(gap > cnt) return false;
        else return true;
    }
};
#include <iostream>
using namespace std;

int n,m,x,y;

//创建dp表
long long dp[25][25]; // 防止数据溢出

int main() 
{
    cin >> n >> m >> x >> y;
    //由于dp表规模是 n + 1, m + 1 对应x、y也要 + 1
    x += 1; y += 1; //映射关系
    
    //初始化
    dp[0][1] = 1;
    
    for(int i = 1; i <= n + 1; i++)
    {
        for(int j = 1; j <= m + 1; j++)
        {
            //分情况讨论
            if((i == x && j == y) || x != i && y != j && abs(i - x) + abs(j - y) == 3)
                dp[i][j] = 0;
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];                
        }
        
    }
    
   cout << dp[n + 1][m + 1] << endl;
    
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

int main() 
{
    long long n, m, a, b;
    cin >> n >> m >> a >> b;

    long long ret = -0x3f3f3f3f;

    for(int i = 0; i <= min(n / 2, m); i++)
    {
        int j = min(n - 2 * i, (m - i) / 2);
        ret = max(ret, i * a + j * b);
    }
    cout << ret << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")


#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() 
{
    string str;
    getline(cin,str);
    //整体逆序
    reverse(str.begin(), str.end());
    //局部每个单词逆序

    int start = 0;
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == ' ')
        {
            //逆序
            reverse(str.begin() + start, str.begin() + i);
            start = i + 1;
        }
    }

    reverse(str.begin() + start, str.begin() + str.size());
    cout << str << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

    int maxLength(vector<int>& arr) 
    {
        //滑动窗口
        vector<int> hash(100020);
        int ret = 1;
        int left = 0, right = 0;
        while(right < arr.size())
        {
            // 进窗口
            hash[arr[right]]++;
            //判断
            while(hash[arr[right]] > 1)
            {
                hash[arr[left++]]--;
            }
            //更新结果
            ret = max(ret, right - left + 1);
            right++;
        }   
        return ret;
    }

    #include <iostream>
#include <algorithm>
using namespace std;

int n;
long long arr[300030];
int main() 
{
    cin >> n;

    for(int i = 0; i < 3 * n; i++)
    {
        cin >> arr[i];
    }

    sort(arr, arr + 3 * n);

    int j = 3 * n - 2;
    long long ret = 0;
    while(n--)
    {
        ret += arr[j];
        j -= 2;
    }

    cout << ret << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

int boredom(vector<int>& a) 
    {
        const int N = 1e4 + 10;

        int hash[N] = {0};

        //预处理数组,所有数的和累加起来
        for(int i : a)
        {
            hash[i] += i;
        }

        //创建dp表
        vector<int> f(N), g(N);
        
        //f[i]表示：选到i时，i位置必选，此时的最大分数
        //g[i]表示：选到i时，i位置不选，此时的最大分数

        // 初始化
        f[0] = g[0] = 0;
        
        //填表
        for(int i = 1; i < N; i++)
        {
            f[i] = hash[i] + g[i - 1];
            g[i] =max(f[i - 1], g[i - 1]);
        }

        return max(f[N - 1], g[N - 1]);
    }


//
//  main.cpp
//  test
//
//  Created by s1nzz xie on 2025/4/9.
//

#include <iostream>
#include <unordered_map>

using namespace std;

int n,m;

unordered_map<int, int> has;

bool check(int x) // 判断最多人数为x时，能否分成m组
{
    int g = 0; // 能分成多少组
    for(auto& [a, b] : has)
    {
        g += b / x + (b % x == 0 ? 0 : 1);
    }
    return g <= m;
}

int main(int argc, const char * argv[]) {
    cin >> n >> m;
    
    //统计各个声部人数
    int hmax = -1;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        hmax = max(hmax, ++has[x]);
    }
    
    int kinds = has.size();
    if(kinds > m)
    {
        //处理边界情况
        cout << -1 << endl;
    }
    else
    {
//        //暴力枚举
//        for(int i = 1; i <= hmax; i++)
//        {
//            if(check(i))
//            {
//                cout << i << endl;
//                break;
//            }
//        }
        
        //二分查找
        int l = 0, r = hmax;
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(check(mid))
               r = mid;
           else
               l = mid + 1;
        }
        cout << l << endl;
    }
    
    
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 2e5 + 10;

vector<vector<int>> edges(N); // edges[i] 表示i这个点所连接的所有边信息
int in[N] = {0}; // 存储入度信息

queue<int> q;
vector<int> ret;
int n,m;

int main() 
{
    cin >> n >> m;

    //建图：用容器将数据存储起来
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b); // 存储边信息
        in[b]++; //存储入度信息
    }

    //把所有入度为0的点加入到队列中
    for(int i = 1; i <= n; i++)
    {
        if(in[i] == 0)
        {
            q.push(i);
        }
    }

    while(q.size())
    {
        //取出队头元素，并添加到结果容器中
        int f = q.front();
        q.pop();
        ret.push_back(f);

        //修改对应边入度的信息
        for(int b : edges[f])
        {
            //入度为0则添加到队列中
            if(--in[b] == 0)
            {
                q.push(b);
            }
        }
    }

    if(ret.size() == n)
    {
        for(int i = 0; i < n - 1; i++)
        {
            cout << ret[i] << " ";
        }
        cout << ret[n - 1];
    }
    else {
        cout << -1 << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")

#include <iostream>
#include <string>
using namespace std;

string str;
int x;

int main() {
    cin >> str >> x;
    int begin = -1; // 记录结果的起始位置
    int maxCnt = 0; // 统计 C 和 G 的最大个数
    int cnt = 0;    // 统计 C 和 G 的个数
    int left = 0, right = 0;
    int n = str.size();
    while(right < n)
    {
        //进窗口
        if(str[right] == 'C' || str[right] == 'G')
            cnt++;

        //判断
        while(right - left + 1 > x)
        {
            // 出窗口
            if(str[left] == 'G' || str[left] == 'C')
                cnt--;
            
            left++;
        }

        if(right - left + 1 == x)
        {
            //更新结果
            if(maxCnt < cnt)
            {
                cnt = maxCnt;
                begin = left;
            }
        }

        right++;
    }

    cout << str.substr(begin, x) << endl;


    return 0;
}
// 64 位输出请用 printf("%lld")

 #include<iostream>
 #include<cstdio>
 #include<vector>

using namespace std;

int n, m;

int main()
{
    cin >> n >> m;
    
    vector<vector<long long>> arr(n, vector<long long>(m));
    vector<long long>row(n), col(m);
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            scanf("%ld", &arr[i][j]);
            
            //预处理
            row[i] += arr[i][j];
            col[j] += arr[i][j];
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cout << col[j] + row[i] - arr[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}


#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 1e5+10;
int n, k;

LL h[N], s[N];

int main()
{
    //输入数据
    cin >> n >> k;
    
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> s[i];
    
    //滑动窗口
    int left = 1, right = 1;
    LL hSum = 0, sSum = 0, begin = 0,hMax = 0, sMin = 0;
    
    while(right <= n)
    {
        //进窗口
        hSum += h[right];
        sSum += s[right];
        
        //判断
        while(right - left + 1 > k)
        {
            //出窗口
            hSum -= h[left];
            sSum -= s[left];
            left++;
        }
        
        //更新结果
        if(right - left + 1 == k)
        {
            if(hSum > hMax)
            {
                begin = left;
                hMax = hSum;
                sMin = sSum;
            }
            else if(hSum == hMax && sMin > sSum)
            {
                begin = left;
                hMax = hSum;
                sMin = sSum;
            }
        }
        
        right++;
    }
    
    cout << begin << endl;
    return 0;
}

#include <iostream>
using namespace std;

int n, a;

int gcd(int a, int b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}

int main() 
{
    while(cin >> n >> a)
    {
        for(int i = 0; i < n; i++)
        {
            int b;
            cin >> b;
            if(a >= b)
            {
                a += b;
            }
            else {
                a += gcd(a, b);
            }
        }
        cout << a << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) 
    {
        int m = grid.size(), n = grid[0].size();

        //创建dp表
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        //无需初始化

        //填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
                dp[i][j] += grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

#include <iostream>
#include <vector>

using namespace std;

int n;

int main()
{
    cin >> n;
    
    while(n--)
    {
        int m;
        cin >> m;
        vector<string> vs(m);
        vector<vector<int>> hashs(m,vector<int>(26,0)); // 统计字符出现的次数
        for(int i = 0; i < m; i++)
        {
            cin >> vs[i];
            for(char ch : vs[i])
                hashs[i][ch - 'a']++;
        }
        
        int left = 0, right = m - 1;
        while(left < right)
        {
            int f1 = 0;
            for(int i = 0; i < 26;i++)
            {
                if(hashs[left][i] && hashs[right][i])
                {
                    left++;
                    right--;
                    f1 = 1;
                    break;
                }
            }
            if(!f1) 
            {
                break;
            }
        }
        
        if(left >= right)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
        
    }
    
    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

long long a,h,b,k;

int main()
{
    cin >> a >> h >> b >> k;
    long long ret = 0;
    //计算互砍次数
    int n = min(k / a, h / b);
    ret += n * (b + a);
    //求出剩余的血量
    h -= n * b;
    k -= n * a;
     
    //判断是否还活着
    if(h > 0 && k > 0)
    {
        h -= b;
        ret += b;
        k -= a;
        ret += a;
    }
    
    //判断是否需要放大招
    if(h > 0 || k > 0)
    {
        ret += 10 * (h > 0 ? a : b);
    }
    
    cout << ret << endl;
    return 0;
}

#include <iostream>
using namespace std;

const int N = 2e5 + 10;

int n;
int arr[N];
int dp[N];

int main() {
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    int ret = -101;
    //动态规划
    for(int i = 1; i <= n; i++)
    {
        dp[i] = max(dp[i - 1], 0) + arr[i - 1];
        ret = max(ret, dp[i]);
    }
    cout << ret << endl;
    return 0;
}
// 64 位输出请用 printf("%lld") 

#include<iostream>
#include<string>

using namespace std;

string str;
int n = 0;

int func()
{
    // 判断是否为重复元素构成的字符串
    bool flag = false;
    for(int i = 1; i < n; i++)
    {
        if(str[i] != str[i - 1])
            flag = true;
    }
    if(!flag) return 0;
    
    //求回文字符串的长度
    int left = 0, right = n - 1;
    while(left < right)
    {
        if(str[left] == str[right])
        {
            left++;
            right--;
        }
        else
        {
            flag = false;
            break;
        }
    }
    
    if(flag) return n - 1;
    else return n;
    
}

int main()
{
    cin >> str;
    n = str.size();
    cout << func() << endl;
    return 0;
}

#include <iostream>
#include <string>

int dp[1001][1001];

using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();
    for(int i = n - 1; i >= 0; i--)
    {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; j++)
        {
            if(str[i] == str[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else
                dp[i][j] = max(dp[i+1][j], dp[i][j - 1]);
        }
    }

    cout << dp[0][n - 1] << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

#include <iostream>
#include <string>

using namespace std;

string a, b;

int main() {
    cin >> a >> b;
    int m = a.size(), n = b.size();
    int ret = m;
    //暴力枚举
    for(int i = 0; i <= n - m; i++)
    {
        int tmp = m;
        for(int j = 0; j < m; j++)
        {
            if(a[j] == b[i + j])
            {
                tmp--;
            }
        }
        ret = min(ret, tmp);
    }
    cout << ret << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

#include <iostream>
using namespace std;

int arr[50];
int n;

int main() {
    cin >> n;
    int max = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
        if(arr[i] > max)
            max = arr[i];// 找到最大值
    }
    int flag = 0;
    for(int i = 0; i < n; i++)
    {
        int x = max / arr[i];
        //(x & x - 1) 是判断当前数是否是2的n次方的方法
        if(max % arr[i] != 0 || (x & x - 1))
        {
            if(arr[i] != 1)
            {
                flag = 1;
                break;
            }
        }
    }
    if(!flag)
        cout << "YES" << endl;
    else 
        cout << "NO" << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

#include<iostream>
#include<vector>

using namespace std;
const int N = 2e4+5, M = 35;
int n,v; 
int arr[M];
int dp[M][N];
int main()
{
    cin >> v >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= v; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= arr[i])
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i]] + arr[i]);
            }
        }
    }
    cout << (v - dp[n][v]) << endl;
    return 0;
}